AlgorithmJourney/LeetCode/LeetCode200.java at main · HenryJi529/AlgorithmJourney · GitHub

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import java.util.Arrays;
import java.util.HashSet;

public class LeetCode200 {
    public static void main(String[] args) {
        // 输入：grid = [
        // ['1','1','1','1','0'],
        // ['1','1','0','1','0'],
        // ['1','1','0','0','0'],
        // ['0','0','0','0','0']
        // ]
        // 输出：1
        System.out.println(new Solution200_1().numIslands(new char[][] {
                { '1', '1', '1', '1', '0' },
                { '1', '1', '0', '1', '0' },
                { '1', '1', '0', '0', '0' },
                { '0', '0', '0', '0', '0' }
        }));

        // 输入：grid = [
        // ['1','1','0','0','0'],
        // ['1','1','0','0','0'],
        // ['0','0','1','0','0'],
        // ['0','0','0','1','1']
        // ]
        // 输出：3
        System.out.println(new Solution200_1().numIslands(new char[][] {
                { '1', '1', '0', '0', '0' },
                { '1', '1', '0', '0', '0' },
                { '0', '0', '1', '0', '0' },
                { '0', '0', '0', '1', '1' }
        }));
    }
}

class Solution200_1 {
    boolean[][] visited;
    int num = 0;
    char[][] grid;
    int m;
    int n;
    int[][] dirs = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    public int numIslands(char[][] grid) {
        this.grid = 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 (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(i, j);
                    num++;
                }
            }
        }
        return this.num;
    }

    public void dfs(int x, int y) {
        visited[x][y] = true;
        for (int[] dir : dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                // System.out.println(newNode[0] + " " + newNode[1]);
                if (grid[newX][newY] == '1' && !visited[newX][newY]) {
                    dfs(newX, newY);
                }
            }
        }
    }
}

class Solution200_2 {
    // NOTE: 构建一个用内容计算hashcode的HashSet，但没啥用
    HashSet<IntArrayWrapper> visited = new HashSet<>();
    int num = 0;
    char[][] grid;
    int m;
    int n;
    int[][] dirs = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    class IntArrayWrapper {
        private final int[] array;

        public IntArrayWrapper(int[] array) {
            this.array = array;
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(array);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null || getClass() != obj.getClass()) {
                return false;
            }
            IntArrayWrapper other = (IntArrayWrapper) obj;
            return Arrays.equals(array, other.array);
        }
    }

    public int numIslands(char[][] grid) {
        this.grid = 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' && !visited.contains(new IntArrayWrapper(new int[] { i, j }))) {
                    dfs(new int[] { i, j });
                    num++;
                }
            }
        }
        return this.num;
    }

    public void dfs(int[] node) {
        visited.add(new IntArrayWrapper(node));
        for (int[] dir : dirs) {
            int[] newNode = new int[] { node[0] + dir[0], node[1] + dir[1] };
            if (newNode[0] >= 0 && newNode[0] < m && newNode[1] >= 0 && newNode[1] < n) {
                // System.out.println(newNode[0] + " " + newNode[1]);
                if (grid[newNode[0]][newNode[1]] == '1' && !visited.contains(new IntArrayWrapper(newNode))) {
                    dfs(newNode);
                }
            }
        }
    }
}

class LeetCode200_3 {
    // NOTE: 也可以直接把访问过的节点变成'0': grid[i][j] = '0'
}