算法八 搜索（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;
    }
}