LeetCode代码日记(五)

图论首次学习企划

LeetCode797: 所有可能路径

图论开始的第一道题，dfs经典作品: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        path.add(0);
        dfs(graph, 0);
        return result;
    }
    private void dfs(int[][] graph, int start) {
        if (path.getLast() == graph.length - 1) {
            result.add(new ArrayList<>(path));
            return;
        }
        int[] tmp = graph[start];
        for (int i = 0; i < tmp.length; i++) {
            path.add(tmp[i]);
            dfs(graph, tmp[i]);
            path.removeLast();
        }
    }

LeetCode200: 岛屿数量

dfs/bfs/并查集的经典题目:
深度优先搜索: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 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
private boolean[][] used;
    int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int numIslands(char[][] grid) {
        int ans = 0;
        used = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (!used[i][j] && grid[i][j] == '1') {
                    bfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
    private void bfs(char[][] grid, int  y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        used[y][x] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
            int nexty = cur[0] + move[i][0];
            int nextx = cur[1] + move[i][1];
            if (nexty < 0 || nexty >= grid.length || nextx < 0 || nextx >= grid[0].length || used[nexty][nextx] || grid[nexty][nextx] == '0') continue;
            queue.offer(new int[]{nexty, nextx});
            used[nexty][nextx] = true;
            }
        }
    }

LeetCode1020: 飞地的数量

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
private boolean[][] used;
   private int[] tmp = new int[2];
   public int numEnclaves(int[][] grid) {
       used = new boolean[grid.length][grid[0].length];
       int res = 0;
       for (int i = 1; i < grid.length; i++) {
           for (int j = 1; j < grid[0].length; j++) {
               if (!used[i][j] && grid[i][j] == 1) {
                   dfs(grid, i, j);
                   if (tmp[0] != 1) res += tmp[1]; //没碰到边界然后再计算
                   tmp = new int[2];
               }
           }
       }
       return res;
   }
   private void dfs(int[][] grid, int y, int x) {
       if (used[y][x] || grid[y][x] == 0) return;
       used[y][x] = true;
       //碰到边界 一切结束
       if (y == 0 || y == grid.length - 1 || x == 0 || x == grid[0].length - 1) {
           tmp[0] = 1;
           return;
       }
       tmp[1]++;
       dfs(grid, y + 1, x);
       dfs(grid, y - 1, x);
       dfs(grid, y, x + 1);
       dfs(grid, y, x - 1);
   }

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
private boolean[][] used;
   private int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
   public int numEnclaves(int[][] grid) {
       int res = 0;
       used = new boolean[grid.length][grid[0].length];
       for (int i = 1; i < grid.length - 1; i++) {
           for (int j = 1; j < grid[0].length - 1; j++) {
               if (!used[i][j] && grid[i][j] == 1) {
                   int[] tmp = bfs(grid, i, j);
                   if (tmp[0] == 0) res += tmp[1];
               }
           }
       }
       return res;
   }
   private int[] bfs(int[][] grid, int y, int x) {
       int[] tmp = new int[2];
       Queue<int[]> queue = new LinkedList<>();
       queue.offer(new int[]{y, x});
       used[y][x] = true;
       tmp[1] = 1;
       while (!queue.isEmpty()) {
          int[] cur = queue.poll();
          for (int i = 0; i < 4; i++) {
              int nexty = cur[0] + move[i][0];
              int nextx = cur[1] + move[i][1];
              if (nexty < 0 || nexty >= grid.length || nextx < 0 || nextx >= grid[0].length || grid[nexty][nextx] == 0 || used[nexty][nextx] == true) continue;
              if (nexty == 0 || nexty == grid.length - 1 || nextx == 0 || nextx == grid[0].length - 1) {
                  tmp[0] = 1;
              }
              used[nexty][nextx] = true;
              queue.offer(new int[]{nexty, nextx});
              tmp[1]++;
          }
       }
       return tmp;
   }

LeetCode130: 被围绕的区域

BFS: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private boolean[][] used;
   private int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   public void solve(char[][] board) {
       used = new boolean[board.length][board[0].length];
       for (int i = 1; i < board.length - 1; i++) {
           for (int j = 1; j < board[0].length - 1; j++) {
               if (!used[i][j] && board[i][j] == 'O') {
                   List<int[]> list =  bfs(board, i, j);
                   for (int [] q : list) {
                       board[q[0]][q[1]] = 'X';
                   }
               }
           }
       }
   }
   private List<int[]> bfs(char[][] board, int y, int x) {

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
private boolean flag;
    private boolean[][] used;
    private List<int[]> list = new ArrayList<>();
    public void solve(char[][] board) {
        used = new boolean[board.length][board[0].length];
        for (int i = 1; i < board.length -1; i++) {
            for (int j = 1; j < board[0].length - 1; j++) {
                if (!used[i][j] && board[i][j] == 'O') {
                    dfs(board, i, j);
                    if (!flag) {
                        for (int[] p : list) {
                            board[p[0]][p[1]] = 'X';
                        }
                    }
                    flag = false;
                    list.clear();
                }
            }
        }
    }
    private void dfs(char[][]board, int y, int x) {
        if (used[y][x] || board[y][x] == 'X') return;
        if (y == 0 || y == board.length - 1 || x == 0 || x == board[0].length - 1) {
            list.clear();
            flag = true;
            return;
        }
        used[y][x] = true;
        list.add(new int[]{y, x});
        dfs(board, y - 1, x);
        dfs(board, y + 1, x);
        dfs(board, y, x + 1);
        dfs(board, y, x - 1);
    }

LeetCode417: 太平洋大西洋水流问题

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
private boolean[] test = new boolean[2];
   private boolean[][] used;
   private List<List<Integer>> result = new ArrayList<>();
   private int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   public List<List<Integer>> pacificAtlantic(int[][] heights) {
      for (int i = 0; i < heights.length; i++) {
          for (int j = 0; j < heights[0].length; j++) {
              used = new boolean[heights.length][heights[0].length];
              test[0] = false;
              test[1] = false;
              dfs(heights, i, j);
              if (test[0] && test[1]) result.add(List.of(i, j));
              
          }
      }
      return result;
   }
   private void dfs(int[][] heights, int y, int x) {
       if (test[0] && test[1]) return;
       if (x < 0 || x >= heights[0].length || y < 0 || y >= heights.length || used[y][x]) return;
       used[y][x] = true;
       if (x == 0 || y == 0) test[0] = true;
       if (x == heights[0].length - 1 || y == heights.length - 1) test[1] = true;
       if (y + 1 < heights.length && heights[y][x] >= heights[y + 1][x]) dfs(heights, y + 1, x);
       if (y - 1 >= 0 && heights[y][x] >= heights[y - 1][x]) dfs(heights, y - 1, x);
       if (x + 1 < heights[0].length && heights[y][x] >= heights[y][x + 1]) dfs(heights, y, x + 1);
       if (x - 1 >= 0 && heights[y][x] >= heights[y][x - 1]) dfs(heights, y, x - 1);
   }

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
private boolean[] test = new boolean[2];
    private boolean[][] used;
    private List<List<Integer>> result = new ArrayList<>();
    private int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
       for (int i = 0; i < heights.length; i++) {
           for (int j = 0; j < heights[0].length; j++) {
               used = new boolean[heights.length][heights[0].length];
               test[0] = false;
               test[1] = false;
               bfs(heights, i, j);
               if (test[0] && test[1]) result.add(List.of(i, j));
               
           }
       }
       return result;
    }
    private void bfs(int[][] heights, int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        if (x == 0 || y == 0) test[0] = true;
        if (x == heights[0].length - 1 || y == heights.length - 1) test[1] = true;
        if (test[0] && test[1]) return;
        used[y][x] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nexty = cur[0] + move[i][0];
                int nextx = cur[1] + move[i][1];
                if (nexty < 0 || nexty >= heights.length || nextx < 0 || nextx >= heights[0].length || used[nexty][nextx] || heights[cur[0]][cur[1]] < heights[nexty][nextx]) continue;
                if (nextx == 0 || nexty == 0) test[0] = true;
                if (nextx == heights[0].length - 1 || nexty == heights.length - 1) test[1] = true;
                if (test[0] && test[1]) return;
                used[nexty][nextx] = true;
                queue.offer(new int[]{nexty, nextx});

            }
        }

    }

LeetCode827: 最大人工岛

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
57
58
private int mark = 2;
private boolean[][] used;
private int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int largestIsland(int[][] grid) {
    used = new boolean[grid.length][grid[0].length];
    HashMap<Integer, Integer> hp = new HashMap<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (!used[i][j] && grid[i][j] == 1) {
                hp.put(mark, bfs(grid, i, j));
                mark++;
            }
        }
    }
    int max = 0;
    for (Map.Entry<Integer, Integer> entry : hp.entrySet()) {
        max = Math.max(max, entry.getValue());
    }
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] != 0) continue;
            int size = 1;
            HashSet<Integer> hashSet = new HashSet<>();
            for (int k = 0; k < 4; k++) {
                int nexty = i + move[k][0];
                int nextx = j + move[k][1];
                if (nexty < 0 || nexty >= grid.length || nextx < 0 || nextx >= grid[0].length  || grid[nexty][nextx] == 0) continue;
                if (!hashSet.contains(grid[nexty][nextx])) {
                    hashSet.add(grid[nexty][nextx]);
                    size += hp.get(grid[nexty][nextx]); 
                }
            }
            max = Math.max(max, size);
        }
    }
    return max;
}
private int bfs(int[][] grid, int y, int x) {
    int res = 0;
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{y, x});
    grid[y][x] = mark;
    res++;
    used[y][x] = true;
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        for (int i = 0; i < 4; i++) {
            int nexty = cur[0] + move[i][0];
            int nextx = cur[1] + move[i][1];
            if (nexty < 0 || nexty >= grid.length || nextx < 0 || nextx >= grid[0].length || used[nexty][nextx] || grid[nexty][nextx] == 0) continue;
            queue.offer(new int[]{nexty, nextx});
            used[nexty][nextx] = true;
            grid[nexty][nextx] = mark;
            res++;
        }
    }
    return res;
}

LeetCode1971: 寻找图中是否存在路径

并查集的基础题目: 

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 boolean validPath(int n, int[][] edges, int source, int destination) {
        UnionFind unionFind = new UnionFind(n);
        for (int[] edge : edges) {
            unionFind.join(edge[0], edge[1]);
        }
        return unionFind.isSame(source, destination);
    }
}
public class UnionFind {
    private int n;
    private int[] father;
    //初始化
    public UnionFind(int n) {
        this.n = n;
        this.father = new int[n];
        for (int  i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    //并查集寻根过程
    public int find(int u) {
        if (u == father[u]) return u;
        return father[u] = find(father[u]);
    }
    //判断u和v是否找到同一个根
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    //将u->v这条边加入到并查集
    public void join(int u, int v) {
        u = find(u);//寻找u的根
        v = find(v);//寻找v的根
        if (u == v) return;
        father[v] = u;
    }
}

LeetCode648: 冗余连接

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[] findRedundantConnection(int[][] edges) {
        UnionFind unionFind = new UnionFind();
        for (int[] edge : edges) {
            if (unionFind.isSame(edge[0], edge[1])) return edge;
            unionFind.join(edge[0], edge[1]);
        }
        return null;
    }
}
public class UnionFind {
    private int n = 1005;
    private int[] father;
    //初始化
    public UnionFind() {
        this.father = new int[n];
        for (int  i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    //并查集寻根过程
    public int find(int u) {
        if (u == father[u]) return u;
        return father[u] = find(father[u]);
    }
    //判断u和v是否找到同一个根
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    //将u->v这条边加入到并查集
    public void join(int u, int v) {
        u = find(u);//寻找u的根
        v = find(v);//寻找v的根
        if (u == v) return;
        father[v] = u;
    }
}
Leetcode
#代码练习日记
LeetCode代码日记(五)
http://example.com/2023/11/08/LeetCode代码日记-五/
作者
John Doe
发布于
2023年11月8日
许可协议