Leetcode 200. 岛屿数量 / 547. 省份数量
1.1 题目描述
- 题目链接：200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例1：
输入: grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出: 1
示例2：
输入: grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出: 3
1.2 思路
- 深度优先搜索
逐行遍历整个二维数组，遇到1就计数器加1,然后将其该格的数值置为0,并搜索其周围是否还有其它为1的格子，重复搜索-置0直至周围没有为1的格子就继续返回并遍历数组。
class Solution {
public:
void dfs(vector<vector<char>>& grid, int row, int col){
int n_row = grid.size(), n_col = grid[0].size();
grid[row][col] = '0';
if(row - 1 >= 0 && grid[row-1][col] == '1') dfs(grid, row-1, col);
if(col - 1 >= 0 && grid[row][col-1] == '1') dfs(grid, row, col-1);
if(row + 1 < n_row && grid[row+1][col] == '1') dfs(grid, row+1, col);
if(col + 1 < n_col && grid[row][col+1] == '1') dfs(grid, row, col+1);
}
int numIslands(vector<vector<char>>& grid) {
int n_row = grid.size();
if(n_row == 0) return 0;
int n_col = grid[0].size();
int cnt = 0;
for(int row = 0; row < n_row; ++row){
for(int col = 0; col < n_col; ++col){
if(grid[row][col] == '1'){
++cnt;
dfs(grid, row, col);
}
}
}
return cnt;
}
};- 广度优先搜索
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size(), nc = grid[0].size();
if(!nr || ! nr) return 0;
int res = 0;
for(int r = 0; r < nr; ++r){
for(int c = 0; c < nc; ++c){
if(grid[r][c] == '1'){
++res;
grid[r][c] = '0'; //置为0
queue<pair<int,int>> q;
q.push({r,c}); //将节点加入队列
while(!q.empty()){
auto iter = q.front(); //创建迭代器
q.pop();
int row = iter.first, col = iter.second;
if(row - 1 >= 0 && grid[row-1][col] == '1'){
q.push({row-1, col});
grid[row-1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col-1] == '1'){
q.push({row, col-1});
grid[row][col-1] = '0';
}
if(row + 1 < nr && grid[row+1][col] == '1'){
q.push({row+1, col});
grid[row+1][col] = '0';
}
if(col + 1 < nc && grid[row][col+1] == '1'){
q.push({row, col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return res;
}
};- 并查集
将整个grid展平为一个数组，那么我们要求的其实就是这个数组中相互连在一起的个数，即图中的连通块个数。那么可以遍历整个grid，当grid[r][c]为1时初始化fa[r*m+c]=r*m+c即fa[i]=i并将岛屿数量count加1，而当grid[r][c]不为1时，随便将f[i]置一个数，因为后边不会用到也不会访问到这个下标；完成初始化后就进行grid的遍历，如果当前的grid[r][c]为1，那么就检查它四周的四个点是否为1，为1则进行连接并将岛屿数量count减1，完成遍历后count即为实际的岛屿数量。
class Solution {
int n, m;
int count;
vector<int> fa, rank; // 父节点数组，秩数组
// 初始化fa数组
void init(vector<vector<char>>& grid) {
count = 0;
int n = grid.size(), m = grid[0].size();
for(int r = 0; r < n; ++r) {
for(int c = 0; c < m; ++c) {
if(grid[r][c] == '1')
fa.emplace_back(r*m + c), ++count;
else
fa.emplace_back(-1);
rank.emplace_back(0); // 初始化高为0
}
}
}
int find(int x) {
return fa[x]==x ? x: (fa[x] = find(fa[x])); // 路径压缩
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx != fy) {
if(rank[fx] <= rank[fy])
fa[fx] = fy;
else {
fa[fy] = fx;
if(rank[fx] == rank[fy]) ++rank[fy];
--count; // 进行连通，岛屿数量-1
}
}
public:
int numIslands(vector<vector<char>>& grid) {
n = grid.size(), m = grid[0].size();
fa.clear(), rank.clear();
/*初始化fa数组*/
init(grid);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(grid[i][j] =='1') {
// 判断是否要进行连通
if(i-1>=0 && grid[i-1][j]=='1') merge(i*m+j, (i-1)*m+j);
if(j-1>=0 && grid[i][j-1]=='1') merge(i*m+j, i*m+j-1);
if(i+1<n && grid[i+1][j]=='1') merge(i*m+j, (i+1)*m+j);
if(j+1<m && grid[i][j+1]=='1') merge(i*m+j, i*m+j+1);
}
}
}
return count;
}
};这里实际上只需要对为
1的点的右和下两个方向进行判断，因为其他两个方向实际上在前边以及后续的遍历中都会遍历到。
2.1 题目描述
- 题目链接：547. 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量.
示例1:
输入: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出: 2
示例2:
输入: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出: 3
2.2 思路
- 深度优先搜索
创建一个 bool 类型的 visited 数组来表示某个城市是否已经访问过了，并初始化为 false，因为一开始所有的城市都未被访问过。然后按行遍历数组 isConnected, 当某一位为 1 时，说明有其他城市与之相邻，那么将 visited[i](下标i指当前遍历的是第i个城市)置为 true，然后到与之相接的那个城市，即那一行进行遍历，重复过程: 找到为 1 的城市就把visited[i] 置为 true并跳到对应的那一行进行遍历直至访问的城市再没有为 1 的城市就返回继续按行遍历，如果遍历第 i 行时有 visited[i] == true 则直接跳过下一行，否则结果 res 加 1.
class Solution {
public:
void dfs(vector<vector<int>>& isConnected, vector<int>& tmp, int i){
tmp[i] = 1;
for(int j = 0; j < isConnected.size(); ++j){
if(isConnected[i][j] == 1 && tmp[j] == 0){
dfs(isConnected, tmp, j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int res = 0;
vector<int> tmp(n);
for(int i = 0; i < n; i++){
if(tmp[i] == 0){
++res;
dfs(isConnected, tmp, i);
}
}
return res;
}
};广度优先搜索
class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n = isConnected.size(); bool visited[n]; memset(visited, false, sizeof(visited)); int res = 0; for(int i = 0; i < n; ++i){ if(visited[i] == false){ visited[i] = true; ++res; queue<int> q; q.push(i); while(!q.empty()){ int row = q.front(); q.pop(); for(int col = 0; col < n; ++col){ if(!visited[col] && isConnected[row][col] == 1){ q.push(col); visited[col] = true; } } } } } return res; } };并查集
这道题实际上就是求大小为n的图中有多少个连通块，建立一个fa[n]父数组，然后初始化为其本身即fa[i] = i，然后由于isConnected必定是沿主对角线对称的，因而可以只遍历左上角，当检测到isConnected[i][j]==1时说明i和j是连在一起，因而进行merge(i,j)，并将数量n视情况减1，最后返回n即可。
class Solution {
int n, count;
vector<int> fa, rank;
int find(int x) {
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx != fy) {
if(rank[fx] <= rank[fy])
fa[fx] = fy;
else
fa[fy] = fx;
if(rank[fx] == rank[fy]) ++rank[fy];
--count;
}
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
n = isConnected.size(), count = n;
fa = vector<int>(n);
for(int i = 0; i < n; ++i) fa[i] = i;
rank = vector<int>(n, 0);
for(int i = 0; i < n-1; ++i) for(int j = i+1; j < n; ++j)
if(isConnected[i][j] == 1)
merge(i, j);
return count;
}
};
