05 August 2008
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
1
2
3
4
5
6
7
Input:
11110
11010
11000
00000
Output: 1
Example 2:
1
2
3
4
5
6
7
Input:
11000
11000
00100
00011
Output: 3
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 int numIslands(char[][] grid) {
int result = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return result;
}
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
result++;
dfs(grid, i, j, rows, cols);
}
}
}
return result;
}
private void dfs(char[][] grid, int i, int j, int rows, int cols) {
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1') {
return;
}
grid[i][j] = '0'; //每次找到一块陆地就变为‘0’。以防重复查找
dfs(grid, i + 1, j, rows, cols);
dfs(grid, i - 1, j, rows, cols);
dfs(grid, i, j + 1, rows, cols);
dfs(grid, i, j - 1, rows, cols);
}
}
BFS，这里用了额外的一个2D数组来存储是否已经访问过，如果可以改变原数组的值，则可以不要visited数组。
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
class Solution {
public int numIslands(char[][] grid) {
int result = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return result;
}
int rows = grid.length;
int cols = grid[0].length;
// 四个方向扩散
int[][] directions = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
// 标记已经已经访问过
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 如果是岛屿中的一个点，并且没有被访问过
// 从坐标为 (i,j) 的点开始进行BFS
if (!visited[i][j] && grid[i][j] == '1') {
result++;
LinkedList<Integer> queue = new LinkedList<>(); // 扩散中每一圈的元素
// 这里在queue中把当前元素的坐标转换成一个数字，不然就得用一个数组来存储当前的元素的坐标
// 坐标转换类似于2D数组中的二分查找
queue.offerLast(i * cols + j);
visited[i][j] = true; //标记访问过
while (!queue.isEmpty()) {
int current = queue.pollFirst();
// 根据上面存储的数字进行坐标转换
int curX = current / cols;
int curY = current % cols;
// 得到需要扩散的四个方向的x,y坐标
for (int k = 0; k < 4; k++) {
int newX = curX + directions[k][0];
int newY = curY + directions[k][1];
// 扩散中如果不越界、没有被访问过、并且还是岛屿，就继续放入队列，同时要记得标记已经访问过
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
grid[newX][newY] == '1' &&
!visited[newX][newY]) {
queue.offerLast(newX * cols + newY); //扩散中的元素的坐标仍然转换为数字
visited[newX][newY] = true;
}
}
}
}
}
}
return result;
}
}
Union Find，整体思路：
1. 实现Union Find函数
2. 循环元素值 并判断下侧和右侧是否为岛屿
如果 是：合并元素值
如果 否：不做处理
1
3. 将海洋对应的nums数组位置设为-2
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
class Solution {
public int numIslands(char[][] grid) {
//DFS
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int[] parent = new int[rows * cols]; // 存储每个连通分量的最终父节点
Arrays.fill(parent, -1);
for(int i = 0; i < rows;i++){
for(int j = 0; j < cols; j++){
if(grid[i][j] == '1'){
parent[i * cols + j]= i * cols + j; // note, that `parent` was filled witn -1 values
if(i > 0 && grid[i - 1][j] == '1') { // 与左边比较
union(i * cols + j, (i - 1) * cols + j, parent); // union current+top
}
if(j > 0 && grid[i][j - 1] == '1') { // 与上面比较
union(i * cols + j, i * cols + (j - 1), parent); // union current+left
}
}
}
}
Set<Integer> set = new HashSet<>();
for(int k = 0; k < parent.length; k++){
if(parent[k] != -1) {
set.add(find(k, parent)); // 寻找多少个圈子
}
}
return set.size();
}
// 以下为并查集的路径压缩代码
private int find(int p, int[] parent) {
if (parent[p] == p) {
return p;
}
parent[p] = find(parent[p], parent); // 路径压缩，使find的时间复杂度为O(1)
return parent[p];
}
private void union(int p1, int p2, int[] parent) {
int f1 = find(p1, parent);
int f2 = find(p2, parent);
if (f1 != f2) {
parent[f1] = f2;
}
}
}
检查右侧和下侧也可以，写法比较灵活
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
class Solution {
public int numIslands(char[][] grid) {
int result = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return result;
}
int rows = grid.length;
int cols = grid[0].length;
// 1维数组存储连通后剩余岛屿的数量(-1)，以及连通后的水域(0, -2)
int[] nums = new int[rows * cols];
// 初始值，不连通或自连通
Arrays.fill(nums, -1);
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(grid[i][j] == '1') {
grid[i][j] = '0'; // 不用额外数组，先把自己修改一下
//判断下侧是否有岛屿,同BFS解法中的坐标转换为数字
if(i < (rows - 1) && grid[i + 1][j] == '1') {
union(nums, i * cols + j, (i + 1) * cols + j);
}
//判断右侧是否有岛屿,同BFS解法中的坐标转换为数字
if(j < (cols - 1) && grid[i][j + 1] == '1') {
union(nums, i * cols + j, i * cols + j + 1);
}
} else {
nums[i * cols + j] = -2;
}
}
}
for(int num : nums) { // 检查岛屿个数
if(num == -1) {
result++;
}
}
return result;
}
public int find(int[] parents, int i) {
if(parents[i] == -1) { // 连通
return i;
}
return find(parents, parents[i]);
}
public void union(int[] parents, int x, int y) {
int xset = find(parents, x);
int yset = find(parents, y);
if(xset != yset) {
parents[xset] = yset;
}
}
}