Maze Problem

130. 被围绕的区域

​

方法一：DFS

  1. 从边界出发，把边界以及与边界连通的O标记为B`

  2. 遍历整个board，把B还原为O，把O(此时的O是被X包围的)改变为X

  3. 没有这句死循环，m == 1，( i += 0)

        if (m <= 2 || n <= 2)
        return;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        if (m <= 2 || n <= 2)
            return;
        for (int i = 0; i < m; i += m - 1) 
            for (int j = 0; j < n; ++j) 
                if (board[i][j] == 'O')
                    dfs(i, j, board);
        for (int j = 0; j < n; j += n - 1)
            for (int i = 0; i < m; ++i)
                if (board[i][j] == 'O')
                    dfs(i, j, board);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'B')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    
    private void dfs(int i, int j, char[][] board) {
        board[i][j] = 'B'; // backtrack
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && board[row][col] == 'O')
                dfs(row, col, board);
        }
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
    
}

方法二：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public void solve(char[][] board) {
        this.board = board;
        m = board.length;
        n = board[0].length;
        if (m <= 2 || n <= 2)
            return;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i += m - 1)
            for (int j = 0; j < n; ++j)
                if (board[i][j] == 'O')
                    queue.offer(new int[]{i, j});
                    
        for (int j = 0; j < n; j += n - 1)
            for (int i = 1; i < m - 1; ++i)
                 if (board[i][j] == 'O')
                    queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            board[node[0]][node[1]] = '#';
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && board[row][col] == 'O')
                    queue.offer(new int[]{row, col});
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '#')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }

    private void dfs(int i, int j) {
        board[i][j] = '#';
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && board[row][col] == 'O') {
                dfs(row, col);
            }
        }
    }


    private boolean isValid(int row, int col) {
        return row < m && row >= 0 && col < n && col >= 0;
    }

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    char[][] board;
}

方法三：并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package 背包;


import java.awt.image.VolatileImage;

public class Solution {

    public void solve(char[][] board) {
        this.board = board;
        m = board.length;
        n = board[0].length;
        if (m <= 2 || n <= 2)
            return;
        init(m * n + 1);
        int dummy = m * n;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
                        union(n * i + j, dummy);
                    else {
                        for (int[] dir : dirs) {
                            int row = i + dir[0], col = j + dir[1];
                            if (isValid(row, col) && board[row][col] == 'O')
                                union(row * n + col, i * n + j);
                        }
                    }
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O' && findParent(i * n + j) != dummy)
                    board[i][j] = 'X';
            }
        }

    }
    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
    private boolean isValid(int row, int col) {
        return row < m && row >= 0 && col < n && col >= 0;
    }

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    char[][] board;


    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = new char[][]{{'O','O','O'}, {'O','O','O'}, {'O','O','O'}};
        solution.solve(board);
        System.out.println(board);

    }


}

200. 岛屿数量

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    dfs(i, j, grid);
                    ++res;
                }
            }
        }
        return res;
    }

    int res = 0, m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private void dfs(int i, int j, char[][] grid) {
        grid[i][j] = '2';
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == '1')
                dfs(row, col, grid);
        }

    }
    
    private boolean isValid(int i, int j) {
        return i >= 0 && j >=0 && i < m && j < n;
    }
    
}

方法二：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    bfs(queue, i, j, grid);
                    ++res;
                }
            }
        }
        return res;
    }

    int res = 0, m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private void bfs(Queue<int[]> queue, int i, int j, char[][] grid) {
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && grid[row][col] == '1') {
                    grid[row][col] = '2';
                    queue.offer(new int[]{row, col});
                }
            }
        }
       
    }
    
    private boolean isValid(int i, int j) {
        return i >= 0 && j >=0 && i < m && j < n;
    }
    
}

329. 矩阵中的最长递增路径

方法一：DFS + 记忆化搜索

  1. 如果之前计算过dp[i][j]，直接返回dp[i][j]

  2. 计算从matrix[i][j]为起点的最长路径，并用max记录最大值

    1
    2
    if (isValid(row, col) && matrix[row][col] > matrix[i][j]) {
        max = Math.max(max, dfs(row, col, matrix));

  3. 返回上一个节点的时候需要加上1，因为当前节点也需要加上，并用dp[i][j]记录

    1
    return dp[i][j] = max + 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        dp = new int[m][n];
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                res = Math.max(res, dfs(i, j, matrix));
        return res;
    }

    int res = 1, m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, dp;

    private int dfs(int i, int j, int[][] matrix) {
        if (dp[i][j] != 0)
            return dp[i][j];
        int max = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && matrix[row][col] > matrix[i][j]) {
                max = Math.max(max, dfs(row, col, matrix));
            }
        }
        return dp[i][j] = max + 1;
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
    
}

二刷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        this.matrix = matrix;
        dp = new int[m][n];
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                res = Math.max(res, dfs(i, j));
        return res;
    }

    int[][] matrix, dp, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n, res = 0;

    private int dfs(int i, int j) {
        if (dp[i][j] != 0)
            return dp[i][j];
        int max = 1;
        for (int[] dir : dirs) {
            int len = 1;
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && matrix[i][j] < matrix[row][col])
                len = dfs(row, col) + 1;
            max = Math.max(len, max);
        }
        return dp[i][j] = max;
    }
    
    private boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
}

417. 太平洋大西洋水流问题

三刷DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        this.heights = heights;
        boolean[][] pacific = new boolean[m][n], atlantic = new boolean[m][n];
        for (int j = 0; j < n; ++j) {
            dfs(0, j, pacific);
            dfs(m - 1, j, atlantic);
        }
        for (int i = 0; i < m; ++i) {
            dfs(i, 0, pacific);
            dfs(i, n - 1, atlantic);
        }
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j)
                if (pacific[i][j] && atlantic[i][j])
                    res.add(Arrays.asList(i, j));
        return res;
    }

    int[][] heights, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;

    private void dfs(int i, int j, boolean[][] ocean) {
        ocean[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && !ocean[row][col] && heights[row][col] >= heights[i][j]) 
                dfs(row, col, ocean);
        }
    }

    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < m && j < n;
    }
    
}

二刷DFS

把四条边先标记好，然后dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        pacific = new boolean[m][n];
        atlantic = new boolean[m][n];
        for (int j = 0; j < n; ++j)
            pacific[0][j] = true;
        for (int i = 0; i < m; ++i)
            pacific[i][0] = true;
        for (int j = 0; j < n; ++j)
            atlantic[m - 1][j] = true;
        for (int i = 0; i < m; ++i)
            atlantic[i][n - 1] = true;
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                if (pacific[i][j] || atlantic[i][j]) 
                    dfs(i, j, heights);
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                if (pacific[i][j] && atlantic[i][j])
                    res.add(Arrays.asList(i, j));
        return res;
    }
    
    List<List<Integer>> res = new LinkedList<>();
    boolean[][] pacific, atlantic;
    int m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
     
     private void dfs(int i, int j, int[][]heights) {
         for (int[] dir : dirs) {
             int row = i + dir[0], col = j + dir[1];
             if (isValid(row, col) && heights[row][col] >= heights[i][j]) {
                if (pacific[i][j] && !pacific[row][col]) {
                    pacific[row][col] = true;
                    dfs(row, col, heights);
                }
                if (atlantic[i][j] && !atlantic[row][col]) {
                    atlantic[row][col] = true;
                    dfs(row, col, heights);
                }
             }
         }
     }
    
    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
    
}

463. 岛屿的周长

方法一：DFS

  1. 初始每个陆地的边长都为4，如果周围有一个相连的陆地，那么周长-1，如上图grid[1][1]，上下左右都有陆地，所以它拥有的边长为4 - 4 = 0
  2. 只要陆地i, j的邻居row, col不是水域，那么先将周长减一
    1. 如果grid[row][col] == 2，说明之前访问过，不需要继续dfs，但是需要讲周长减一
    2. 如果grid[row][col] == 1，周长需要减一并且需要dfs访问
1
2
3
4
if (isValid(row, col) && grid[row][col] != 0) {
   --length;
   if (grid[row][col] == 1)
       dfs(row, col, grid);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int islandPerimeter(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                if (grid[i][j] == 1) 
                    dfs(i, j, grid);
        return res;
    }

    int res = 0, m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private void dfs(int i, int j, int[][] grid) {
        grid[i][j] = 2;
        int length = 4;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] != 0) {
                --length;
                if (grid[row][col] == 1)
                    dfs(row, col, grid);
            }
        }
        res += length; 
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
    
}

方法二：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int islandPerimeter(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    grid[i][j] = 2;
                    bfs(i, j, grid, queue);
                    return res;
                }
        return -1;
    }

    int res = 0, m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private void bfs(int i, int j, int[][] grid, Queue<int[]> queue) {
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int length = 4;
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && grid[row][col] != 0) {
                    --length;
                    if (grid[row][col] == 1) {
                        grid[row][col] = 2;
                        queue.offer(new int[]{row, col});
                    }
                }
            }
            res += length;
        }
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

695. 岛屿的最大面积

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1)
                    res = Math.max(res, dfs(i, j, grid));
        return res;
    }
    
    int m, n, res = 0;
    int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    
    private int dfs(int i, int j, int[][] grid) {
        int length = 1;
        grid[i][j] = 2;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == 1)
                length += dfs(row, col, grid);
        }
        return length;
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

方法二：并查集

注意

  1. 只有当grid[i][j] == 1时才判断

    1. 如果row,col不超过边界，且grid[row][col]是陆地(1或者2)，且没有被访问过(如果访问过，

      那么grid[i][j]与grid[row][col]的parent一致)，则将grid[i][j]赋值2(1表示没有被访问的陆地，2表示被访问过的陆地)

    2. 如果row,col不超过边界，且grid[row][col]是陆地(1或者2)，但是被访问过(此时也会绑定grid[i][j]与grid[row][col]的parent)，不执行

    1
    2
    3
    4
    5
    6
    7
    8
     if (grid[i][j] == 1) {
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            // 1.不超过边界 2.是陆地 3.没有被访问过
            if (isValid(row, col) && grid[row][col] != 0 && union(i * n + j, row * n + col))
                grid[i][j] = 2;
        }
    }

  2. 遍历所有陆地，将每块陆地的祖先存入map，值为子孙的数量，那么含有最大子孙的数量就是岛屿最大数量

    map进行put操作时，key为findParent(i * n + j)，因为在之前进行union的过程(parent[parentOfI] = parentOfJ)，直接将i的祖先的祖先赋值为j的祖先，但是此时i的祖先还没有同步，所以这里是进行一个祖先同步的操作

    1
    2
    3
    4
    5
    6
    7
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < m; ++i) 
        for (int j = 0; j < n; ++j) 
            if (grid[i][j] != 0) {
                map.put(findParent(i * n + j), map.getOrDefault(parent[i * n + j], 0) + 1);
                res = Math.max(res, map.get(parent[i * n + j]));
            }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        init(m, n);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    for (int[] dir : dirs) {
                        int row = i + dir[0], col = j + dir[1];
                        // 1.不超过边界 2.是陆地 3.没有被访问过
                        if (isValid(row, col) && grid[row][col] != 0 && union(i * n + j, row * n + col))
                            grid[i][j] = 2;
                    }
                }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                if (grid[i][j] != 0) {
                    map.put(findParent(i * n + j), map.getOrDefault(parent[i * n + j], 0) + 1);
                    res = Math.max(res, map.get(parent[i * n + j]));
                }
        return res;
    }

    int m, n, res = 0;
    int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    int[] parent;

    private void init(int m, int n) {
        parent = new int[m * n];
        for (int i = 0; i < m * n; ++i)
            parent[i] = i;
    }
    private int findParent(int i) {
        return i == parent[i] ? parent[i] : (parent[i] = findParent(parent[i]));
    }

    private boolean union(int i, int j) {
        int parentOfI = findParent(i), parentOfJ = findParent(j);
        if (parentOfI != parentOfJ) {
            parent[parentOfI] = parentOfJ;
            return true;
        }
        return false;
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

二刷并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        init(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    for (int[] dir : dirs) {
                        int row = i + dir[0], col = j + dir[1];
                        if (isValid(row, col) && grid[row][col] == 1)
                            union(i * n + j, row * n + col);
                    }
                }
            }
        }
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] != 0) {
                    map.put(findParent(i * n + j), map.getOrDefault(parent[i * n + j], 0) + 1);
                    res = Math.max(res, map.get(parent[i * n + j]));
                }
        return res;
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int m, n;
    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

733. 图像渲染

方法一：BFS

二刷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        m = image.length;
        n = image[0].length;
        int targetColor = image[sr][sc];
        image[sr][sc] = color;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        boolean[][] visited = new boolean[m][n];
        visited[sr][sc] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row,col) && !visited[row][col] && image[row][col] == targetColor) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                    image[row][col] = color;
                }
            }
        } 
        return image;
    }

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;    
    }
    
}

一刷

小心死循环，curColor很关键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int curColor = image[sr][sc];
        if (color == curColor)
            return image;
        m = image.length;
        n = image[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = color;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && image[row][col] == curColor) {
                    queue.offer(new int[]{row, col});
                    image[row][col] = color;
                }
            }
        }
        return image;
    }

    int m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < m && j < n;
    }
    
}

方法二：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int curColor = image[sr][sc];
        if (color == curColor)
            return image;
        m = image.length;
        n = image[0].length;
        image[sr][sc] = color;
        dfs(sr, sc, color, curColor, image);
        return image;
    }

    int m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    private void dfs(int i, int j, int color, int curColor, int[][] image) {
        image[i][j] = color;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && image[row][col] == curColor)
                dfs(row, col, color, curColor, image);
        }
    }
    
    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < m && j < n;
    }
    
}

1020. 飞地的数量

方法一：DFS

同太平洋大西洋水流问题，从边缘进入dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        if (m <= 2 || n <= 2)
            return 0;
        for (int i = 0; i < m; i += m - 1)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1)
                    dfs(i, j, grid);
        for (int j = 0; j < n; j += n - 1)
            for (int i = 1; i < m - 1; ++i)
                if (grid[i][j] == 1)
                    dfs(i, j, grid);
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                if (grid[i][j] == 1)
                    ++res;
        return res;
    }

    int res = 0, m, n;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    private void dfs(int i, int j, int[][] grid) {
        grid[i][j] = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == 1)
                dfs(row, col, grid);
        }
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

}

方法二：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int j = 0; j < n; ++j)
            if (grid[0][j] == 1) 
                queue.offer(new int[]{0, j});
        for (int i = 1; i < m; ++i)
            if (grid[i][0] == 1)
                queue.offer(new int[]{i, 0});
        for (int i = 1; i < m; ++i)
            if (grid[i][n - 1] == 1)
                queue.offer(new int[]{i, n - 1});
        for (int j = 1; j < n - 1; ++j)
            if (grid[m - 1][j] == 1)
                queue.offer(new int[]{m - 1, j});
        while(!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && grid[row][col] == 1) {
                    grid[row][col] = 0;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        int res = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 1)
                    ++res;
            }
        }
        return res;
    }

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
    
}

1559. 二维网格图中探测环

方法三：并查集

题解

遍历矩阵，只检查左边和上面，可以保证每一条边的两个节点只会被合并一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public boolean containsCycle(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        init(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int[] dir : dirs) {
                    int row = i + dir[0], col = j + dir[1];
                    if (isValid(row,col) && grid[i][j] == grid[row][col]) {
                        if (!union(i * n + j, row * n + col))
                            return true;
                    }
                }
            }
        }
        return false;
    }

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int[][] dirs = new int[][]{{-1, 0}, {0, -1}};
    int m, n;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

方法一：BFS

  1. 每次从队列中取出一个节点时，记录当前队列大小size，初始化neigbors = 0

  2. 在上下左右四个方向遍历，如果相邻节点没有越界且与当前字符相同，++neighbors，如果没访问过，加入队列，visited赋值true

  3. 遍历完四个方向后，如果neigbors - 1== queue.size() - size，(-1是减去上一次访问过，并将当前节点入队的节点)，说明新入队的邻居之前都没有访问过

  4. 如果neigbors - 1 > queue.size() - size，说明遍历到了已经访问过的jie'dian，那么可以形成环

  5. 举例

    从下标(0, 0)开始BFS遍历，有两条路径，一条向右出发(记为路径A)，一条向下出发(记为路径B)，这里默认先遍历右边再遍历下面

    当遍历了5步后，如下图

    (路径A)此时下标为(2, 3)的节点往下遍历，将右下角编号为(3, 3)的节点赋值true，如下图

    (路径B)现在下标为(3, 2)的节点往右遍历，邻居neighbors = 2，但是queue.size() - size = 0(队列没有新入队节点)，说明路径A已经遍历过这个节点了 ，那么路径B可以按照路径A返回起点，所以可以形成环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public boolean containsCycle(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                if (!visited[i][j] && bfs(i, j, grid))
                    return true;
        return false;
    }

    private boolean bfs(int i, int j, char[][] grid) {
        queue.offer(new int[]{i, j});
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int neibors = 0, size = queue.size();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && grid[row][col] == grid[node[0]][node[1]]) {
                    ++neibors;
                    if (!visited[row][col]) {
                        queue.offer(new int[]{row, col});
                        visited[row][col] = true;
                    }
                }
            }
            if (neibors - 1 > queue.size() - size)
                return true;
        }
        return false;
    }

    int m, n;
    boolean[][] visited;
    Queue<int[]> queue = new LinkedList<>();
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < m && j < n;
    }
}

方法二：DFS

通过preI,preJ记录上一个已访问节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean containsCycle(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (!visited[i][j] && dfs(i, j, grid, -1, -1))
                    return true;
        return false;
    }

    private boolean dfs(int i, int j, char[][] grid, int preI, int preJ) {
        if (visited[i][j])
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == grid[i][j]) {
                if (row == preI && col == preJ)
                    continue;
                if (dfs(row, col, grid, i, j))
                    return true;
            }
        }
        return false;
    }

    int m, n;
    boolean[][] visited;
    Queue<int[]> queue = new LinkedList<>();
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < m && j < n;
    }
}

785. 判断二分图

方法一：BFS

colors[next] == 1 - color说明访问过，而且颜色与当前颜色不同，不用加入队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1);
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (colors[i] == -1) {
                colors[i] = 0;
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int node = queue.poll(), color = colors[node];
                    for (int next : graph[node]) {
                        if (colors[next] == -1) {
                            colors[next] = 1 - color;
                            queue.offer(next);
                        }
                       else if (colors[next] == color)
                            return false;
                        }
                    }
                }
            }
            return true;
        }
}

方法二：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1);
        for (int i = 0; i < n; ++i) {
            if (colors[i] == -1) {
                if (!dfs(graph, colors, i, 0))
                    return false;
            }
        }
            return true;
    }

    private boolean dfs(int[][] graph, int[] colors, int i, int color) {
        colors[i] = color;
        for (int next : graph[i]) {
            if (colors[next] == -1) {
                if (!dfs(graph, colors, next, 1 - color))
                    return false;
            }
            else {
                if (colors[next] == color)
                    return false;
            }
        }
        return true;
    }
    
}

方法三：并查集

每个顶点i的邻居应该是在同一个集合里，如果i与邻居在一个集合，则不是二分图

遍历每一个顶点i，判断i与邻居是否在一个集合中，如果是则不是二分图返回false；如果顶点i不与邻居在同一个集合，那么将邻居合并到同一个集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        init(n);
        for (int i = 0; i < n; ++i) {
            for (int next : graph[i]) {
                if (findParent(i) == findParent(next))
                    return false;
                union(graph[i][0], next);
            }
        }
        return true;
    }

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

剑指 Offer II 110. 所有路径

方法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;
        this.graph = graph;
        path.offer(0);
        dfs(0);
        return res;
    }

    private void dfs(int index) {
        if (index == n - 1) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int next : graph[index]) {
            path.offerLast(next);
            dfs(next);
            path.pollLast();
        }

    }

    int n;
    int[][] graph;
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
}

剑指 Offer II 111. 计算除法

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); ++i) {
            String num1 = equations.get(i).get(0), num2 = equations.get(i).get(1);
            graph.putIfAbsent(num1, new HashMap<>());
            graph.putIfAbsent(num2, new HashMap<>());
            graph.get(num1).put(num2, values[i]);
            graph.get(num2).put(num1, 1 / values[i]);
        }
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); ++i) {
            String num1 = queries.get(i).get(0), num2 = queries.get(i).get(1);
            if (!graph.containsKey(num1) || !graph.containsKey(num2))
                res[i] = -1.0;
            else if (num1.equals(num2)) // 字符在图中且两个字符相等
                res[i] = 1.0; 
            else if (graph.get(num1).containsKey(num2))
                res[i] = graph.get(num1).get(num2);
            else {
                visited.clear();
                res[i] = dfs(num1, num2, graph);
            }

        }
        return res;
    }

    Set<String> visited = new HashSet<>();

    private double dfs(String num1, String num2, Map<String, Map<String, Double>> graph) {
        if (num1.equals(num2))
            return 1.0;
        visited.add(num1);
        Map<String, Double> nexts = graph.get(num1);
        for (String next : nexts.keySet()) {
            if (visited.contains(next))
                continue;
            double val = dfs(next, num2, graph);
            if (val > 0)
                return val * nexts.get(next);
        }
        visited.remove(num1);
        return -1.0;
    }
}

二进制矩阵中翻转最多一次使路径不连通

方法一：两次DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean isPossibleToCutPath(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        return !dfs(0, 0) || !dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (i == m - 1 && j == n - 1)
            return true;
        grid[i][j] = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == 1 && dfs(row, col))
                return true;
        }
        return false;
    }


    int m, n;
    int[][] dirs = new int[][]{{1, 0}, {0, 1}}, grid;

    private boolean isValid(int i, int j) {
        return i < m && j < n;
    }
}
Algorithms > Graph
#图 #迷宫问题
Maze Problem
https://leopol1d.github.io/2023/06/05/maze-problem/
作者
Leopold
发布于
2023年6月5日
许可协议