算法八 搜索（Java实现）
刷题时间：2021.9.16-2021.9.24
求最短：宽搜
回溯、尝试、试探：深搜
1、LeetCode200岛屿数量
思路1：(DFS)
1标记当前搜索位置已,被搜索(标记当前位置的mark数组为1)。
2.按照方向数组的4个方向，拓展4个新位置newx、newy。
3.若新位置不在地图范围内，则忽略。
4.如果新位置未曾到达过(mark[newx] [newy]为0)、且是陆地(grid[newx] [newy]为"1"),继续DFS该位置。
LeetCode评论代码
class Solution { public int numIslands(char[][] grid) { int m = grid.length,n = grid[0].length,ans = 0; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(grid[i][j] == '1'){ dfs(grid,i,j,m,n); ans++; } } } return ans; } public void dfs(char[][] grid,int i,int j,int m,int n){ if(i >= m || i < 0 || j >= n || j < 0){ return; } if(grid[i][j] == '0' || grid[i][j] == 'X'){ return; } if(grid[i][j] == '1'){ grid[i][j] = 'X'; } dfs(grid,i + 1,j,m,n); dfs(grid,i - 1,j,m,n); dfs(grid,i,j + 1,m,n); dfs(grid,i,j - 1,m,n); } } 复制代码思路2：(BFS)
1.设置搜索队列Q，标记make[x][y]= 1，并将待搜索的位置(x, y) push进入队列Q。
2.只要队列不空，即取队头元素，按照方向数组的4个方向，拓展4个新位置newx、newy。
3.若新位置不在地图范围内，则忽略。
4.如果新位置未曾到达过(mark[newx] [newy]为0)、且是陆地(grid[newx] [newy]为“1);将该新位置push进入队列，并标记mark[newx] [newy]= 1。
LeetCode官方题解
class Solution { public int numIslands(char[][] grid) { int count = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '1'){ bfs(grid, i, j); count++; } } } return count; } private void bfs(char[][] grid, int i, int j){ Queue<int[]> list = new LinkedList<>(); list.add(new int[] { i, j }); while(!list.isEmpty()){ int[] cur = list.remove(); i = cur[0]; j = cur[1]; if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') { grid[i][j] = '0'; list.add(new int[] { i + 1, j }); list.add(new int[] { i - 1, j }); list.add(new int[] { i, j + 1 }); list.add(new int[] { i, j - 1 }); } } } } 复制代码2、LeetCode473火柴拼正方形
方法一：深度搜索优化与剪枝
优化1:n个火柴杆的总和对4取余需要为0，否则返回假。
优化2:火柴杆按照从大到小的顺序排序，先尝试大的减少回溯可能。
优化3:每次放置时，每条边上不可放置超过总和的1/4长度的火柴杆。
class Solution { public static boolean makesquare(int[] nums) { //总长度必须是4的倍数 int total = 0; for (int num : nums) { total = total + num; } if (nums.length < 4 || total % 4 != 0) { return false; } //从小到大排序 Arrays.sort(nums); //火柴摆放的长度由大到小 return backtrack(nums, total/4, new int[4], nums.length -1); } private static boolean backtrack(int[] nums, int target, int[] bucket, int index) { if (index == -1) { return bucket[0] == target && bucket[1] == target && bucket[2] == target && bucket[3] == target; } for (int i = 0; i < 4; i++) { if (bucket[i] + nums[index] > target) { continue; } bucket[i] = bucket[i] + nums[index]; //当返回true，说明所有火柴放完了，并且也组成了正方形，此时应该停止摆放，也不需要回溯 if (backtrack(nums, target, bucket, index -1)) { return true; } //当前火柴摆放的边不合适，重新摆放 bucket[i] = bucket[i] - nums[index]; } //上一根摆放的不合适，重新摆放 return false; } } 复制代码方法二：位运算法（详见算法四LeetCode78）
1.使用位运算法，构造出所有和为target(总和/ 4)的子集，存储在向量ok subset中， 这些是候选的边组合。
2.遍历所有的ok_ subset， 两两进行对比，如果ok_ set[i]和ok_ set[j]进行 与运算的结果为0，则说明ok_ set[i]和ok_ set[j]表 示的是无交集的两个集合(没有选择同样的火柴棍)，这两个集合可以代表两个可以同时存在的满足条件的边;将ok_ set[]与ok_ set[j]求或， 结果存储在ok_ half中， 它代表所有满足一半结果的情况。
3.遍历所有的ok half, 两两进行对比，如果ok half[i]和ok half[j]进行与运算的结果为0则返回true(说明有4个满足条件的边，即可组成正方形);否则返回false。
class Solution { public static boolean makesquare(int[] nums) { //总长度必须是4的倍数 int sum = 0; for (int num : nums) { sum = sum + num; } if (nums.length < 4 || sum % 4 != 0) { return false; } List<Integer> ok_subset = new ArrayList<Integer>();//所有满足条件的一个边代表的集合 List<Integer> ok_half = new ArrayList<Integer>();//所有满足条件的两个边代表的集合 int all = 1<<nums.length; for(int i=0;i<all;i++){ int sum2 = 0; for(int j=0;j<nums.length;j++){ if ((i & (1 << j)) != 0){ sum2 += nums[j]; } } if(sum2 == target){ ok_subset.add(i); } } for(int i=0;i<ok_subset.size();i++){ for(int j=i+1;j<ok_subset.size();j++){ if((ok_subset.get(i)&ok_subset.get(j))==0){ ok_half.add(ok_subset.get(i)|ok_subset.get(j)); } } } for(int i=0;i<ok_half.size();i++){ for(int j=i+1;j<ok_half.size();j++){ if((ok_half.get(i)&ok_half.get(j))==0){ return true; } } } return false; } }
作者：zust_Isabella
链接：https://juejin.cn/post/7011764992982646791