题目
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
1
2
3
4
5
6 >输入:
>11110
>11010
>11000
>00000
>输出: 1示例 2:
1
2
3
4
5
6
7 >输入:
>11000
>11000
>00100
>00011
>输出: 3
>解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
很有趣的一道题,拿到这种有具体场景的题目之后,首先要把问题抽象成一类问题。这道题实际上用到的是无向图(Graph),对应的vertices是每个元素的值,而edges存在的条件为与当前vertex相邻(上下左右)的vertex的值均为1。而题目中的“岛屿”,实际上就是Connected Components,在Graph中BFS或DFS并且标记分组。
那么我们要做的是,遍历数组,在数组中进行DFS或BFS,目标是所有横纵相连的1的CC的个数。
如何构建Graph?
要构建一张完整的Graph,最少要遍历一遍容器,然而如果对每个vertex都去与相邻vertex比较并构建edge,会导致重复访问。那么如何做到在无重复访问的前提下构建Graph呢?
在构建Graph的时候,我们可以先把输入矩阵看成一张完整的Graph,vertices的含义不变,而edges的含义变为adjacency,也即上下左右只要存在任意元素就算adjacent to,在这张原始Graph的基础上用一遍DFS遍历输入,并用adjacency list representation method来表示具有“水陆连接性”的Graph。
构建好Graph之后,我们就可以根据adjacency list中DFS的顺序再遍历一遍寻找Connected Components了。
其实按照以上思路,已经访问每个节点两次了,那么我们可以直接在构建Graph的过程中标记Connected Components(将节点置零表示Done)。
实现
本来想着按照课上刚学的实现一个图,然而代码写起来对于一道算法题来说过于复杂。参考答案实现的思路就是原地搜索连续的1,搜索完一块就置0;
边界处理:上下左右下标大于零;
dfs递归实现:
- 结束条件:当前节点为0;
- 上下左右有一个是1,dfs;
为了避免搜索时无限递归,要把dfs起点标记为done(置零);
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
int ans = 0;
for(int col=0; col<grid.size(); ++col){
for(int row=0; row<grid[0].size(); ++row){
if(grid[col][row]=='1'){
++ans;
dfs(grid, row, col);
}
}
}
return ans;
}
private:
void dfs(vector<vector<char>>& G, size_t r, size_t c){
if(G[c][r] == 0) return;
G[c][r] = '0';
if(r>0 && G[c][r-1]=='1') dfs(G, r-1, c);
if(r<G[0].size()-1 && G[c][r+1]=='1') dfs(G, r+1, c);
if(c>0 && G[c-1][r]=='1') dfs(G, r, c-1);
if(c<G.size()-1 && G[c+1][r]=='1') dfs(G, r, c+1);
}
};该过程按照数组顺序遍历容器,每个元素只访问一次,时间复杂度
O(N)
,空间复杂度O(N)
,为最差递归深度。P.S. 一个坑,测试用例输入为字符串常量,不能用整形常量比较。
还可以用迭代实现BFS,同样是按数组顺序遍历数组,若当前元素值为1,则将当前元素位置入队(队列表示检测到但还没有完成搜索的元素),开始广度优先搜索,直到队列为空(处理完当前CC的所有元素),寻找下一个为“1”的元素。
并查集代替搜索,就是算法第一章讲到的union find,如果一个位置为
‘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
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
82class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) { // 把所有有效元素序号存进parent
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent.push_back(i * n + j);
++count; // 陆地数量
}
else {
parent.push_back(-1);
}
rank.push_back(0);
}
}
}
int find(int i) {
if (parent[i] != i) { // 父节点是自己表示自己为根节点
parent[i] = find(parent[i]); // 若i不是根节点,
}
return parent[i]; // 返回的是根节点
}
// 开始时每个元素都是父节点,没有子节点
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]) { // 比较两棵树的大小,保证小的插入大的,Weighted Union-find
swap(rootx, rooty);
}
parent[rooty] = rootx; // 把x的根节点作为y的根节点的父节点(y合并到x,压缩路径)
if (rank[rootx] == rank[rooty]) rank[rootx] += 1; // 这里应该是rank[rootx] += rank[rooty];
--count; // 每次合并都会导致岛屿数目-1
}
}
int getCount() const {
return count;
}
private:
vector<int> parent; // parent表示以下标序号存储的元素的父节点
vector<int> rank; // rank表示这个根节点表示的树的大小
int count; // 已知岛屿数量
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
UnionFind uf(grid);
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
}
}
}
return uf.getCount();
}
};
/*
* 作者:LeetCode
* 链接:https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu- * liang-by-leetcode/
* 来源:力扣(LeetCode)
* 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/