Time: 2021.9.16-2021.9.24

Seek the shortest: wide search

Backtrack, try, probe: search deeply

1. Number of LeetCode200 islands

Idea 1 :(DFS)

1 indicates that the current location is searched (the mark array marking the current location is 1).

2. Expand four new positions newx and newy in the four directions array.

3. If the new location is not in the map, ignore it.

4. If the new location has not been reached (mark[newx] [newy] is 0) and it is land (Grid [newx] [newy] is “1”), continue to DFS the location.

LeetCode Comment code

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); }}Copy the code

Idea 2 :(BFS)

1. Set search queue Q, mark make[x][y]= 1, and push the search position (x, y) into queue Q.

2. As long as the queue is not empty, take the first element of the queue and expand four new positions newx and newy according to the four directions of the array.

3. If the new location is not in the map, ignore it.

4. If the new location has not been reached (mark[newx] [newy] is 0) and it is land (grid[newx] [newy] is “1”); Push the new location into the queue and mark[newx] [newy]= 1.

LeetCode official solution

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}); }}}}Copy the code

2. Match LeetCode473 square

Method 1: deep search optimization and pruning

Optimization 1: The sum of n matchsticks mod 4 needs to be 0, otherwise return false.

Optimization 2: The matchsticks are sorted in order from largest to smallest, and try to reduce backtracking as much as possible first.

Optimization 3: Do not place more than 1/4 of the match sticks on each side of each placement.

class Solution {
public static boolean makesquare(int[] nums) {
        The total length must be a multiple of 4
        int total = 0;
        for (int num : nums) {
            total = total + num;
        }
        if (nums.length < 4 || total % 4! =0) {
            return false;
        }
        // Sort from smallest to largest
        Arrays.sort(nums);
        // The size of the matches goes from large to small
        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];
            // When true is returned, all matches have been placed and formed a square, and should be stopped without backtracking
            if (backtrack(nums, target, bucket, index -1)) {
                return true;
            }
            // The current match side is not suitable, rearrange
            bucket[i] = bucket[i] - nums[index];
        }
        // The last one is not suitable, rearrange
        return false; }}Copy the code

Method 2: bit operation (see Algorithm 4 LeetCode78)

1. Construct all subsets with sum as target(sum / 4) using bit operation and store them in vector OK subset, which are candidate edge combinations.

2. Iterate through all the ok_ subset, and comparison between the two if ok_ set and ok_ set [j] [I] with the result of the operation is 0, then ok_ set [I] and ok_ set [j] table is no intersection of two sets (don’t choose the same matchstick), These two sets can represent two edges that can exist at the same time. Ok_ set[] or ok_ set[j], and the result is stored in ok_ half, which represents all cases where half of the result is satisfied.

If ok half[I] and ok half[j] are equal to 0, then return true. Otherwise return false.

class Solution {
public static boolean makesquare(int[] nums) {
        The total length must be a multiple of 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>();// The set of all edges that satisfy the condition
        List<Integer> ok_half = new ArrayList<Integer>();// The set of two edges that satisfy the condition
        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; }}Copy the code