LeetCodeHot100_0x08
60. 单词搜索
解题思路： 遍历矩阵，找到第一个字母符合的位置，进行dfs深搜。在dfs深搜中，递归出口是将所有的字母都匹配成功，返回true。递归过程是对四个方向进行搜索，判断越界条件、是否访问条件、以及字母是否匹配条件，均符合即可进入下一层方向的递归，只要四个方向中存在一个为true的递归，那就证明该单词可匹配成功，返回true。时刻记得标记数组的标记与撤销。
class Solution {public boolean[][] visited;public int m,n;// 左 下 右 上int[] dx = {0,1,0,-1};int[] dy = {1,0,-1,0};public boolean exist(char[][] board, String word) {// dfs好说m = board.length;n = board[0].length;visited = new boolean[m][n];for(int i=0;i<m;i++) {for(int j=0;j<n;j++) {if(board[i][j] == word.charAt(0)) { // 第一个匹配的才会进入后续visited[i][j] = true;if(dfs(board,i,j,1,word)) {return true; // 遇到true的就立马终止}visited[i][j] = false; // 记得回溯} }}return false;}public boolean dfs(char[][] board,int x,int y,int start, String word) {if( start == word.length()) { // 递归出口return true;}// 四方向搜寻for(int i=0;i<4;i++) {int u = x + dx[i];int v = y + dy[i];// 判断符合条件if(u >=0 && u < m && v >=0 && v < n && !visited[u][v] && board[u][v] == word.charAt(start)) {visited[u][v] = true;if(dfs(board,u,v,start+1,word)) return true; // 遇到true立马终止visited[u][v] = false; // 回溯}}return false;}
}
61. 分割回文串(PDD二面 不会)
求解思路： 最害怕的串和回溯结合起来，完全没有思路。这题是看了答案后进行理解才明白的，接下来讲讲我理解后的思路见解：
首先，要确保分割的子串所有都是回文串，我们需要进行两个动作，即
分割子串 、判断回文
如何如何判断回文呢? 常规的方法当然可以，但是时间复杂度就很高。这题可以通过动态规划来预处理回文子串，具体的分三类情况讨论：
- 只有一个字符：必定是回文串，即
dp[i][j] = true, i==j - 只有两个字符：相等为回文串，即
dp[i][j] = s[i] == s[j] , j==i+1 - 大于两个字符：头尾相同、上层回文，即：
dp[i][j] = (s[i]==s[j] && dp[i+1][j-1]
如何分割字符串呢？ 这就可以用dfs了，不断进行分割，直到分出当前的子串为回文串时，尝试加入答案路径，并进行下一层分割，如果最后不符合，进行回溯。
class Solution {boolean[][] dp; // 动态规划 dp[i][j] 为判断 从i到j的字符串是否为回文串List<List<String>> res = new ArrayList<>(); // 存储答案List<String> path = new ArrayList<>(); // 记录路径/**先是通过预处理将回文串的位置都给标记出来，主要分有三类：第一：单一字符都是一个回文串即：d[i][j] = (i == j)第二：如果只有两个字符，且字符相等，也是一个回文串即: d[i][j] = (j=i+1 && s[i] == s[j]);第三：对于长度大于两个的子串，如果首尾字符相同且上一层是回文字符串即：d[i][j] = (s[i]==s[j] && d[i+1]d[j-1])其次通过搜索分割方式去对字符串进行分割，判断是否都符合回文要求，不符合进行回溯*/public List<List<String>> partition(String s) {//1. 初始化int n = s.length(); dp = new boolean[n][n];//2. 动态规划预处理回文// 单个字符：i == j 时，dp[i][j] == true;// 两个字符相同：j == i+1 && s[i] == s[j] 时，dp[i][j] = true;// 大于两个字符：dp[i][j] = s[i]==s[j] && dp[i+1][j-1];// 计算dp[i][j]时需要先知道dp[i+1][j-1]的值，因此要从较小的子问题开始解决,所以要逆序填表for (int i = n-1; i >= 0; i--) {for (int j = i; j < n; j++) {if(i == j) dp[i][j] = true;else if(j==i+1 && s.charAt(i) == s.charAt(j)) dp[i][j] = true;else dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]);}}//3. 搜索回溯dfs_back(s, 0);return res;}// 搜索回溯函数private void dfs_back(String s, int start) {// 终止条件，分割完了if (start == s.length()) {res.add(new ArrayList<>(path));return;}for (int end = start; end < s.length(); end++) {// 当前子串是回文if (dp[start][end]) { path.add(s.substring(start, end+1)); // 加入路径dfs_back(s, end+1); // 递归分割剩余部分path.remove(path.size()-1); // 回溯}}}
}
62. N皇后
求解思路： 判断n皇后问题主要是保证以下条件：不同行、不同列、不同对角线。其中，不同行通过递归参数保证，即每一层递归会确保在不同行进行。不同列由循环保证，每一层递归都会对列进行循环判断。不同对角线通过集合标记判断。
class Solution {private List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {// 判断皇后可不可以放的三个条件// （1）不同行：遍历行保证// （2）不同列：利用cols集合保证// （3）不同斜线：正反斜线分别通过diag1 和 diag2 集合保证int[] queens = new int[n]; // 索引为行号，值为列号Set<Integer> cols = new HashSet<>(); // 记录已经占用的列Set<Integer> diag1 = new HashSet<>(); // 记录已经占用的正斜线Set<Integer> diag2 = new HashSet<>(); // 记录已经占用的反斜线// 进行回溯backtrack(n,0,queens,cols,diag1,diag2);return res;}private void backtrack(int n,int row,int[] queens,Set<Integer>cols,Set<Integer> diag1,Set<Integer>diag2) {//1. 递归终止条件if(row == n) { // 行已经遍历完，证明皇后防止完毕res.add(listToStringlist(queens,n));return;}//2. 开始按列遍历for(int col=0;col<n;col++) {int d1 = row - col;int d2 = row + col;if(cols.contains(col) || diag1.contains(d1) || diag2.contains(d2)) {continue;}// 尝试放置皇后queens[row] = col;cols.add(col);diag1.add(d1);diag2.add(d2);// 进入下一层递归backtrack(n,row + 1, queens,cols,diag1,diag2);// 进行回溯cols.remove(col);diag1.remove(d1);diag2.remove(d2);}}// 生成答案棋盘private List<String> listToStringlist(int[] queens, int n) {List<String> ans = new ArrayList<>();for(int row = 0;row < n;row++) {char[] line = new char[n];Arrays.fill(line,'.');line[queens[row]] = 'Q';ans.add(new String(line));}return ans;}
}
63. 搜索插入位置
求解思路： 这题题目已经明显到爆了，就是直接考察你二分搜索算法，那就根据题目实现出来即可。
class Solution {public int searchInsert(int[] nums, int target) {// ologn 一看就是二分查找int l = 0 , r = nums.length-1;while(l <= r) {int mid = (l + r) / 2;if(nums[mid] > target) r = mid - 1;else if(nums[mid] < target) l = mid + 1;else return mid;}return l;}
}
64. 搜索二维矩阵
求解思路： 前面刷过这题的进阶了，类似双指针维护。大了往同行前面找，小了往下一行找。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {// 我请问这题和前面刷的有啥区别int m = matrix.length;int n = matrix[0].length;int i = 0, j = n - 1;while(i >=0 && i<m && j>=0 && j<n) {if(matrix[i][j] > target) j--; // 大了往前找 else if(matrix[i][j] < target) i++; // 小了往后找else return true;}return false;}
}
65. 在排序数组中查找元素的第一个位置和最后一个位置
求解思路： 考察对二分算法的理解。分别实现找左边位置和找右边位置的二分算法，当然要注意边界处理和二分方式。比如找左边时，中间值取中间偏左，如果当前位置小于目标值，可以左边更新mid + 1（当前位置定然不是target），否则右边更新为mid。找右边时，中间值取中间偏右，如果当前位置大于目标值，右边更新为mid - 1，否则左边更新为mid
class Solution {public int[] searchRange(int[] nums, int target) {if (nums == null || nums.length == 0) return new int[]{-1, -1};return new int[]{searchFirstTarget(nums,target),searchLastTarget(nums,target)};}// 找左边private int searchFirstTarget(int[] nums,int target) {int l = 0,r = nums.length-1;while(l<r) {int mid = l + (r - l) / 2; // 中间值偏左侧if(nums[mid] < target) l = mid + 1;else r = mid;}return nums[l] == target ? l : -1;}// 找右边private int searchLastTarget(int[] nums,int target) {int l = 0,r = nums.length-1;while(l<r) {int mid = l + (r - l + 1) / 2; // 中间值偏右侧if(nums[mid] > target) r= mid - 1;else l = mid;}return nums[r] == target ? r : -1;}
}
66. 搜索旋转排序数组(不会）
求解思路： 这题能知道要用二分算法，但是变式还是有点困难。首先需要判断哪一部分是正常的升序排序，即用
- nums[mid] > nums[r]证明mid在左半段，再判断target是否在0-mid之间，在则更新R，否则更新L
- nums[mid] <= nums[r]证明mid右半段，再判断target是否在mid - len之间，在则更新L，否则更新R
class Solution {public int search(int[] nums, int target) {// 升序排序，值不相同// 使用时间复杂度为O(log n)的二分查找算法解决该问题// 这个问题的特点是：存在局部单调性int n = nums.length;if(n == 1) return nums[0] == target ? 0 : -1;int l = 0, r = n-1;while(l <= r) {int mid = l + ( r - l) / 2;if(nums[mid] == target) return mid;if(nums[mid] > nums[r]) { // mid 在左半段if(nums[l] <= target && target < nums[mid]) { // target 在左半段r = mid - 1;}else { // target 不在左半段l = mid + 1;} }else { // mid 在右半段if(nums[mid] < target && target <= nums[r]) { // target 在右半段l = mid + 1;}else { // target 不在右半段r = mid - 1;} }}return -1;}
}
67. 寻找旋转排序数组中的最小值
求解思路： 正常进行二分查找，注意更新条件与原二分有差别。最小值一定是在翻转的点位，即右半段的起始值。
class Solution {public int findMin(int[] nums) {// 旋转后的数组由两个递增子数组组成，且左半部分的所有元素严格大于右半部分。// 最小值位于右半段的起始位置// 这题还是考察二分算法的变式//例一： 4 5 6 7 0 1 2//例二：11 13 15 17 int n = nums.length;if(n==1) return nums[0];int l = 0, r = n - 1; while(l<r) {int mid = l + (r-l)/2;if(nums[mid] > nums[r]) { l = mid + 1; // 中间元素位于左半段（左半段元素均大于右半段），因此最小值一定在 mid 右侧}else {r = mid; // 中间元素位于右半段或已经是最小值，此时最小值在 mid 左侧或就是 mid}}return nums[r];}
}
68. 寻找两个正序数组的中位数（不会）
求解思路： 暴力解法还能解一解，先合并后找中位数，二分比较难理解，所以我还是去看递归的官解进行思考。
- 首先判断我们的中位数是一个数，还是两个数的平均数，接着进入递归函数。
- 递归参数有五个，分别是两个数组nums1,nums2和当前遍历到的数组指针s1,s2，以及剩余需要判断的元素k
- 递归终止条件有三个
- 如果num1遍历完，那么直接取nums2的后面第k个元素
- 如果num2遍历完，那么直接取nums1的后面第k个元素
- 如果k = 1，即已经到了中位数了，那就返回当前两指针指向的数组值较小的那一个
- 递归过程
- 首先计算两个数组的中间位置，便于比较两者的中间值
- 比较中间值，每次可以安全排除其中一个数组的前k/2个元素（因为较小的部分不可能包含第k小元素）
【递归思路】
class Solution {// 主函数：计算两个有序数组的中位数public double findMedianSortedArrays(int[] nums1, int[] nums2) {int total = nums1.length + nums2.length;if (total % 2 == 1) { // 总长度为奇数时，返回第 (total+1)/2 小的元素return getKth(nums1, 0, nums2, 0, (total + 1) / 2);}// 总长度为偶数时，返回第 k/2 和第 (k/2+1) 小元素的平均值return (getKth(nums1, 0, nums2, 0, total / 2) + getKth(nums1, 0, nums2, 0, total / 2 + 1)) * 0.5;}// 辅助函数：递归寻找两个数组中第k小的元素private int getKth(int[] nums1, int s1, int[] nums2, int s2, int k) {// 递归终止条件1：nums1已遍历完，直接取nums2的第k小元素if (s1 >= nums1.length) return nums2[s2 + k - 1];// 递归终止条件2：nums2已遍历完，直接取nums1的第k小元素if (s2 >= nums2.length) return nums1[s1 + k - 1];// 递归终止条件3：k=1时返回两数组当前头部较小值if (k == 1) return Math.min(nums1[s1], nums2[s2]);// 计算两个数组的中间位置（防止数组越界）int mid1 = s1 + k/2 - 1 < nums1.length ? nums1[s1 + k/2 - 1] : Integer.MAX_VALUE; // 越界时置为最大值int mid2 = s2 + k/2 - 1 < nums2.length ? nums2[s2 + k/2 - 1] : Integer.MAX_VALUE;// 比较中间值，排除不可能包含第k小元素的部分if (mid1 < mid2) { // 排除nums1的前k/2个元素return getKth(nums1, s1 + k/2, nums2, s2, k - k/2);} else { // 排除nums2的前k/2个元素return getKth(nums1, s1, nums2, s2 + k/2, k - k/2);}}
}
69. 有效的括号
加粗样式 一开始想到之前的做过一道回溯相关括号题。就两个无脑思路，先无脑放左括号直到n，再无脑补右括号直到左括号数量。但是这题又有一些不一样。在判断有效括号时，存在一种特殊的情况：嵌套，即 （[)] ，这种情况时不符合的。所以第二个解法的思路是通过栈判断是否存在嵌套，符号不匹配的情况出现。
【错误解法】解答错误 95 / 100 个通过的测试用例
没有考虑到存在交叉相叠的情况
class Solution {public boolean isValid(String s) {// 三种括号配对int[] l = new int[3];int[] r = new int[3];for(int i=0;i<s.length();i++) {char ch = s.charAt(i);switch(ch) {case '(': l[0]++;break;case ')': r[0]++;break;case '[': l[1]++;break;case ']': r[1]++;break;case '{': l[2]++;break;case '}': r[2]++;break; }// 判断是否出现了先摆右括号后摆左括号的非法情况if(r[0] > l[0] || r[1] > l[1] || r[2] > l[2]) return false;}if(l[0] == r[0] && l[1] == r[1] && l[2] == r[2]) return true;return false;}
}
【双端队列结构充当栈解法】
class Solution {public boolean isValid(String s) {Deque<Character> stack =new LinkedList<>();for(int i=0;i<s.length();i++) {char ch = s.charAt(i);// 如果是左括号直接加入if(ch == '(' || ch=='[' || ch=='{') {stack.offerFirst(ch);}else { // 如果是右括号，判断栈顶左括号是否匹配，不匹配存在嵌套if(stack.isEmpty()) return false;char ch2 = stack.getFirst();if(ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}') {stack.pollFirst();}else {return false;}}}if(stack.isEmpty()) return true;return false;}
}
70. 总结
LeetCOdeHot100_0x08的题目都挺有难度的。主要涉及到搜索、二分、递归、栈等常见算法思想。而且在此之上，题目往往没有直接的告诉你要用哪些算法，有些题目可能会比较场景化，需要你抽象出解决问题的思路。例如回文字符串分割这道题。还有大量的二分查找算法，难点在于如何处理好边界条件，什么时候该加1，什么时候不该加1。如果不处理好，很容易照成无限循环。以下对本节题目做简单的回顾：
- 单词搜索
DFS- 这题比较简单，遍历字符矩阵，只要首字母单词符合的，就可以进行上下左右的递归搜索，只要上下左右的递归搜索中存在一条路走通，那就是答案。
- 分割回文串
动态规划、回溯、dfs- 解决两个问题：如何快速判断回文串？如何分割字符串？
- 为了快速判断回文串，提前通过动态规划思路进行预处理
- 只有一个字符：
dp[i][j] = true, i == j - 两个相同的字符：
dp[i][j] = (s[i] == s[j]) , j= i-1 - 大于两个字符：
dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])
- 只有一个字符：
- 分割字符串，可以通过回溯函数: 尝试加入—下层递归----回溯
- N皇后
DFS- 通过Set集合存储列、对角线的存储信息。确保在行遍历的过程中，不会出现非法皇后的放置。递归的出口在于是否能遍历到最后一行。
- 搜索插入位置
二分查找- 简单二分模板题，二分插入位置就行
- 搜索二维矩阵
思维，双指针- 通过i，j指针维护，大了j–，小了i++
- 搜索在有序数组中的第一个位置和最后一个位置
二分查找进阶- 找最左边的二分和找最右边的二分，注意边界条件的书写
- 搜索旋转数组
二分查找变式- 在常规二分的基础上，需要先判断当前mid值在前面的升序区间还是后面的升序区间。两者需要分开考虑。
- 搜索旋转数组中的最小值
二分查找变式- 首先最小值一定出现在旋转节点，也可以理解为右半段的第一个元素。因此这里的二分更新策略和正常二分相反。
- 寻找两个正序数组的中位数
二分、递归- 这题很难理解，递归做法是通过不断的计算中间值比较，进行快速的元素排除。
- 有效的括号
栈- 用栈可以确保左括号先进栈且符号匹配防止嵌套两个条件，最终栈为空证明左右括号完全匹配成功。