05 August 2008
一个 n x n 二进制矩阵网格。最多可以将一个 0 更改为 1。
此操作后返回网格中最大岛屿的大小。
岛是一个 1 的 4 向连接组。
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 {
/*
https://leetcode.com/problems/making-a-large-island/discuss/127256/DFS-JAVA-AC-CONCISE-SOLUTION
#200 #305 number of islands
*/
public int largestIsland(int[][] grid) {
int max = 0, m = grid.length, n = grid[0].length;
boolean hasZero = false; // to check if there is any zero in the grid
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 0) {
grid[i][j] = 1;
max = Math.max(max, dfs(i, j, grid, new boolean[m][n]));
if (max == m * n) {
return max;
}
grid[i][j] = 0;
hasZero = true;
}
}
}
return hasZero ? max : m * n;
}
private int dfs(int i, int j, int[][] grid, boolean[][] visited) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0 || visited[i][j]) {
return 0;
}
visited[i][j] = true;
int result = 1 + dfs(i-1, j, grid, visited) + dfs(i+1, j, grid, visited) + dfs(i, j+1, grid, visited) + dfs(i, j-1, grid, visited);
return result;
}
}
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
class Solution {
public int largestIsland(int[][] grid) {
if (grid == null || grid.length == 0) return 1;
int result = 0;
int index = 2;
HashMap<Integer, Integer> indexAndAreas = new HashMap<>();
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
int area = area(grid, r, c, index);
indexAndAreas.put(index, area);
index++;
result = Math.max(result, area);
}
}
}
System.out.println(result);
if (result == 0) return 1;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 0) {//遍历海洋格子
HashSet<Integer> hashSet = findNeighbour(grid, r, c);
if (hashSet.size() < 1) continue;
int twoIsland = 1;
for (Integer i : hashSet) twoIsland += indexAndAreas.get(i);
result = Math.max(result, twoIsland);
}
}
}
return result;
}
private HashSet<Integer> findNeighbour(int[][] grid, int r, int c) {
HashSet<Integer> hashSet = new HashSet<>();
if (inArea(grid, r - 1, c) && grid[r - 1][c] != 0)
hashSet.add(grid[r - 1][c]);
if (inArea(grid, r + 1, c) && grid[r + 1][c] != 0)
hashSet.add(grid[r + 1][c]);
if (inArea(grid, r, c - 1) && grid[r][c - 1] != 0)
hashSet.add(grid[r][c - 1]);
if (inArea(grid, r, c + 1) && grid[r][c + 1] != 0)
hashSet.add(grid[r][c + 1]);
return hashSet;
}
private int area(int[][] grid, int r, int c, int index) {
if (!inArea(grid, r, c)) return 0;
if (grid[r][c] != 1) return 0;
grid[r][c] = index;
return 1 + area(grid, r - 1, c, index) + area(grid, r + 1, c, index) + area(grid, r, c - 1, index) + area(grid, r, c + 1, index);
}
private boolean inArea(int[][] grid, int r, int c) {
return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
}
}
UF
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
class Solution {
int[] root;
int[] height;
int[] area;
final int[][] directions = new int[][]{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // 逆时针方向
boolean[] visited;
public int largestIsland(int[][] grid) {
int len = grid.length;
int rowLen = grid[0].length;
int numLen = len * rowLen;
root = new int[numLen];
height = new int[numLen];
area = new int[numLen];
visited = new boolean[numLen];
// initialize
for (int y = 0; y < len; y++) {
for (int x = 0; x < rowLen; x++) {
if (grid[y][x] == 1) {
int index = y * rowLen + x;
root[index] = index;
// height[index] = 0;
area[index] = 1;
}
}
}
// solve
for (int y = 0; y < len; y++) {
for (int x = 0; x < rowLen; x++) {
if (grid[y][x] == 1) {
int index1 = y * rowLen + x;
visited[index1] = true;
for (int[] direction : directions) {
int nextY = y + direction[0], nextX = x + direction[1];
int index2 = nextY * rowLen + nextX;
if (((0 <= nextY && nextY < len) && (0 <= nextX && nextX < rowLen)) && (!(visited[index2]) && grid[nextY][nextX] == 1)) {
union(index1, index2);
}
}
}
}
}
// initialize the ans
int ans = 0;
for (int num : area) ans = Math.max(ans, num + 1);
if (ans == 1) return ans;
for (int y = 0; y < len; y++) {
for (int x = 0; x < rowLen; x++) {
if (grid[y][x] == 0) {
int temp = 1;
Set<Integer> curVisited = new HashSet<>();
for (int[] direction : directions) {
int nextY = y + direction[0], nextX = x + direction[1];
int index = nextY * rowLen + nextX;
if (((0 <= nextY && nextY < len) && (0 <= nextX && nextX < rowLen)) && ((grid[nextY][nextX] != 0) && !curVisited.contains(find(index)))) {
int cur = find(index);
curVisited.add(cur);
temp += area[cur];
}
}
ans = Math.max(ans, temp);
}
}
}
return Math.min(ans, numLen);
}
private void union(int index1, int index2) {
int root1 = find(index1), root2 = find(index2);
if (root1 != root2) {
if (height[root1] > height[root2]) {
root[root2] = root1;
area[root1] += area[root2];
} else if (height[root1] < height[root2]) {
root[root1] = root2;
area[root2] += area[root1];
} else { // height[root1] == height[root2]
root[root2] = root1;
height[root1] += 1;
area[root1] += area[root2];
}
}
}
private int find(int index) {
while (root[index] != index) index = root[index];
return index;
}
}