hot100 [特殊字符]p0——图论，回溯，二分查找

图论岛屿数量200. 岛屿数量 - 力扣LeetCode给你一个由1陆地和0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 1输入grid [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ]输出1示例 2输入grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]输出3解法及思路遍历网格遇到1就计数1然后用 DFS 把整座岛淹掉标记为0。1. 遍历每个格子 2. 遇到 1岛屿数1DFS把相连的1都标记为0 3. 继续遍历直到所有格子处理完 4. 返回岛屿数关键DFS 把整座岛标记为0避免重复计数输入1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1遍历(0,0)1岛屿数1DFS淹掉整个岛 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 遍历(2,2)1岛屿数2DFS淹掉 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 遍历(3,3)1岛屿数3DFS淹掉 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 结果3 ✅class Solution { public int numIslands(char[][] grid) { if(gridnull||grid.length0) return 0; int mgrid.length;//行 int ngrid[0].length;//列 int count0; //遍历每个格子 for(int i0;im;i){ for(int j0;jn;j){ if(grid[i][j]1){ count;//岛数1 dfs(grid,i,j);//淹掉整座岛 } } } return count; } //dfs,淹掉整座岛 public void dfs(char[][] grid,int i,int j){ //越界返回 if(i0||igrid.length||j0||jgrid[0].length) return; //不是1返回 if(grid[i][j]!1) return; //标记为0 grid[i][j]0; //四个方向继续 dfs(grid,i1,j);//下 dfs(grid,i-1,j);//上 dfs(grid,i,j1);//右 dfs(grid,i,j-1);//左 } }回溯全排列46. 全排列 - 力扣LeetCode给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。示例 1输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2输入nums [0,1]输出[[0,1],[1,0]]示例 3输入nums [1]输出[[1]]解法及思路回溯回溯 递归 撤销选择。1. 从前往后每次选一个还没用过的数字 2. 选完后递归处理剩下的数字 3. 递归返回后撤销选择尝试其他数字图解选择1 → 选择2 → 选择3 → 得到一个排列 [1,2,3] ↓ 撤销3 选择3 → 选择2 → 得到一个排列 [1,3,2] ↓ 撤销 选择2 → ... 像一棵树每个节点是一个选择输入[1, 2, 3]backtrack([], used[false,false,false]): i0: 选1 used[true,false,false], path[1] backtrack([1]): i0: used[0]true跳过 i1: 选2 used[true,true,false], path[1,2] backtrack([1,2]): i0,1: 跳过 i2: 选3 used[true,true,true], path[1,2,3] backtrack([1,2,3]): path.size()3 → result.add([1,2,3]) 撤销path[1,2], used[true,true,false] 撤销path[1], used[true,false,false] i2: 选3 used[true,false,true], path[1,3] backtrack([1,3]): i0: 跳过 i1: 选2 path[1,3,2] result.add([1,3,2]) ... i1: 选2 ... i2: 选3 ... 结果[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]class Solution { public ListListInteger permute(int[] nums) { ListListInteger resultnew ArrayList(); boolean[] usednew boolean[nums.length]; backtrack(nums,used,new ArrayList(),result); return result; } public void backtrack(int[] nums,boolean[] used, ListInteger path,ListListInteger result){ //终止条件路径长度等于数组长度 if(path.size()nums.length){ result.add(new ArrayList(path)); return; } //尝试每个数字 for(int i0;inums.length;i){ if(used[i]) continue;//已使用跳过 //选择 used[i]true; path.add(nums[i]); //递归 backtrack(nums,used,path,result); //撤销选择 path.remove(path.size()-1); used[i]false; } } }1. 主函数ListListInteger result new ArrayList(); boolean[] used new boolean[nums.length]; backtrack(nums, used, new ArrayList(), result); return result;used标记哪些数字已使用。2. 终止条件if (path.size() nums.length) { result.add(new ArrayList(path)); return; }当路径长度等于数组长度说明找到了一个完整排列。注意要new ArrayList(path)复制一份否则后面修改会影响结果。3. 选择 递归 撤销for (int i 0; i nums.length; i) { if (used[i]) continue; // 选择 used[i] true; path.add(nums[i]); // 递归 backtrack(nums, used, path, result); // 撤销选择 path.remove(path.size() - 1); used[i] false; }核心三步1. 选择标记used加入path 2. 递归处理下一步 3. 撤销恢复used移除path子集78. 子集 - 力扣LeetCode给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。示例 1输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2输入nums [0]输出[[],[0]]解法及思路回溯每个元素有两种选择选 或 不选。对于 [1, 2, 3] 1选 或 不选 2选 或 不选 3选 或 不选 共 2³ 8 种组合回溯树[] 选1 / \ 不选1 [1] [] 选2 / \不选2 选2 / \不选2 [1,2] [1] [2] [] ...输入[1, 2, 3]backtrack(0, []): result.add([]) i0: 选1 path[1] backtrack(1, [1]): result.add([1]) i1: 选2 path[1,2] backtrack(2, [1,2]): result.add([1,2]) i2: 选3 path[1,2,3] backtrack(3, [1,2,3]): result.add([1,2,3]) 撤销path[1,2] 撤销path[1] i2: 选3 path[1,3] backtrack(3, [1,3]): result.add([1,3]) 撤销path[1] 撤销path[] i2: 选3 path[3] backtrack(3, [3]): result.add([3]) 撤销path[] i1: 选2 ... 结果[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]每个节点都加入结果。class Solution { public ListListInteger subsets(int[] nums) { ListListInteger resultnew ArrayList(); backtrack(nums,0,new ArrayList(),result); return result; } public void backtrack(int[] nums,int start,ListInteger path,ListListInteger result){ //每个节点都是一个子集加入结果 result.add(new ArrayList(path)); //从start开始选择后面的元素 for(int istart;inums.length;i){ //选择 path.add(nums[i]); //递归 backtrack(nums,i1,path,result); //撤销选择 path.remove(path.size() - 1); } } }1. 主函数ListListInteger result new ArrayList(); backtrack(nums, 0, new ArrayList(), result); return result;2. 每个节点都加入结果result.add(new ArrayList(path));和全排列不同全排列只在叶子节点收集结果子集在每个节点都收集。3. 从 start 开始遍历for (int i start; i nums.length; i) { path.add(nums[i]); backtrack(nums, i 1, path, result); // 注意i1不是 start1 path.remove(path.size() - 1); }start保证不会重复选择前面的元素。选1后只能从2开始选 → 避免[1,2]和[2,1]重复单词搜索79. 单词搜索 - 力扣LeetCode给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED输出true示例 2输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEE输出true示例 3输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCB输出false解法及思路回溯 DFS遍历每个格子作为起点用 DFS 向四个方向搜索。1. 遍历每个格子作为起点 2. 从起点开始DFS 匹配 word 的每个字符 3. 匹配成功继续失败就回溯 4. 找到一个完整匹配就返回 trueboardA B C E S F C S A D E Eword ABCCED从(0,0)A开始 dfs(0,0,0): board[0][0]A word[0]A ✅ 标记(0,0)# dfs(0,1,1): board[0][1]B word[1]B ✅ 标记(0,1)# dfs(0,2,2): board[0][2]C word[2]C ✅ 标记(0,2)# dfs(0,3,3): E ! C ❌ dfs(1,2,3): board[1][2]C word[3]C ✅ 标记(1,2)# dfs(2,2,4): board[2][2]E word[4]E ✅ 标记(2,2)# dfs(2,1,5): board[2][1]D word[5]D ✅ index6 word.length() → return true ✅ 结果trueclass Solution { public boolean exist(char[][] board, String word) { int mboard.length; int nboard[0].length; for(int i0;im;i){ for(int j0;jn;j){ if(dfs(board,word,i,j,0)){ return true; } } } return false; } public boolean dfs(char[][]board,String word,int i,int j,int index){ //匹配完成 if(indexword.length()) return true; //越界或字符不匹配 if(i0||iboard.length||j0||jboard[0].length) return false; if(board[i][j]!word.charAt(index)) return false; //标记为已访问 char tempboard[i][j]; board[i][j]#; //四个方向搜索 boolean founddfs(board,word,i-1,j,index1)|| dfs(board,word,i1,j,index1)|| dfs(board,word,i,j-1,index1)|| dfs(board,word,i,j1,index1); //回溯 board[i][j]temp; return found; } }1. 主函数遍历每个起点for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) { return true; } } } return false;每个格子都可能是起点。2. DFS 终止条件if (index word.length()) return true; // 匹配完成 if (越界) return false; // 越界 if (board[i][j] ! word.charAt(index)) return false; // 不匹配3. 标记已访问char temp board[i][j]; board[i][j] #;用#标记避免重复访问。4. 四个方向搜索boolean found dfs(board, word, i 1, j, index 1) || dfs(board, word, i - 1, j, index 1) || dfs(board, word, i, j 1, index 1) || dfs(board, word, i, j - 1, index 1);5. 恢复回溯board[i][j] temp;搜索完后恢复不影响其他路径。二分查找在排序数组中查找元素的第一个和最后一个位置34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [5,7,7,8,8,10], target 8输出[3,4]示例 2输入nums [5,7,7,8,8,10], target 6输出[-1,-1]示例 3输入nums [], target 0输出[-1,-1]解法及思路二分查找找两个位置1. 左边界第一个 target 的位置 2. 右边界最后一个 target 的位置用两次二分查找分别找左边界和右边界nums [5,7,7,8,8,10], target 8找左边界第一个8 left0, right5 mid2, nums[2]7 8 → left3 mid4, nums[4]8 8 → right3 mid3, nums[3]8 8 → right2 left3 right2 → 左边界3 找右边界最后一个8 left0, right5 mid2, nums[2]7 8 → left3 mid4, nums[4]8 8 → left5 mid3, nums[3]8 8 → left4 left5 right5 → 右边界4 结果[3, 4]class Solution { public int[] searchRange(int[] nums, int target) { int leftfindLeft(nums,target); int rightfindRight(nums,target); return new int[]{left,right}; } //找左边界第一个target的位置 public int findLeft(int [] nums,int target){ int left 0, right nums.length - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { result mid; right mid - 1; // 继续往左找 } else { left mid 1; } } // 检查是否真的等于 target if (result ! -1 nums[result] ! target) return -1; return result; } //找右边界第一个target的位置 public int findRight(int [] nums,int target){ int left 0, right nums.length - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { result mid; left mid 1; // 继续往右找 } else { right mid - 1; } } // 检查是否真的等于 target if (result ! -1 nums[result] ! target) return -1; return result; } }搜索旋转排序数组33. 搜索旋转排序数组 - 力扣LeetCode整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标从 0 开始计数。例如[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回它的下标否则返回-1。你必须设计一个时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [4,5,6,7,0,1,2], target 0输出4示例 2输入nums [4,5,6,7,0,1,2], target 3输出-1示例 3输入nums [1], target 0输出-1解法及思路二分查找 判断有序部分旋转后数组被分成两部分至少有一半是有序的。[4,5,6,7,0,1,2] ↑ ↑ 左半有序 右半有序 以mid为界至少有一半是有序的步骤1. 计算 mid 2. 判断左半 [left, mid] 是否有序 3. 如果左半有序 - target 在左半范围内 → 往左找 - 否则 → 往右找 4. 如果右半有序 - target 在右半范围内 → 往右找 - 否则 → 往左找nums [4,5,6,7,0,1,2], target 0left0, right6 mid3, nums[3]7 左半 [4,5,6,7] 有序 target0 不在 [4,7] 范围内 → 往右找left mid 1 4 left4, right6 mid5, nums[5]1 左半 [0,1] 有序 target0 在 [0,1] 范围内 → 往左找right mid - 1 4 left4, right4 mid4, nums[4]0 target → 返回4 ✅class Solution { public int search(int[] nums, int target) { int left0,rightnums.length-1; while(leftright){ int midleft(right-left)/2; if(nums[mid]target) return mid; //左半部分有序 if(nums[left]nums[mid]){ if(nums[left]targettargetnums[mid]){ rightmid-1;//target在左半 }else{ leftmid1;//target在右半 } } //右半部分有序 else{ if(nums[mid]targettargetnums[right]){ leftmid1;//target在右半 }else{ rightmid-1;//target在左半 } } } return -1; } }