admin 管理员组

文章数量: 887007

979

题目如下

给你一个由 ‘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

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

方法一：深度优先搜索

我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1都会被重新标记为 0。

最终岛屿的数量就是我们进行深度优先搜索的次数。

下面的动画展示了整个算法。




class Solution 
{
private:void dfs(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if (r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);if (r + 1 < nr && grid[r + 1][c] == '1') dfs(grid, r + 1, c);if (c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);if (c + 1 < nc && grid[r][c + 1] == '1') dfs(grid, r, c + 1);}public:int numIslands(vector<vector<char>>& grid){int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r){for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;dfs(grid, r, c);}}}return num_islands;}
};

复杂度分析

时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 M N。

方法二：广度优先搜索

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索结束。

最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;grid[r][c] = '0';queue<pair<int, int>> neighbors;neighbors.push({r, c});while (!neighbors.empty()) {auto rc = neighbors.front();neighbors.pop();int row = rc.first, col = rc.second;if (row - 1 >= 0 && grid[row-1][col] == '1') {neighbors.push({row-1, col});grid[row-1][col] = '0';}if (row + 1 < nr && grid[row+1][col] == '1') {neighbors.push({row+1, col});grid[row+1][col] = '0';}if (col - 1 >= 0 && grid[row][col-1] == '1') {neighbors.push({row, col-1});grid[row][col-1] = '0';}if (col + 1 < nc && grid[row][col+1] == '1') {neighbors.push({row, col+1});grid[row][col+1] = '0';}}}}}return num_islands;}
};

方法三：并查集

同样地，我们也可以使用并查集代替搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其与相邻四个方向上的 11 在并查集中进行合并。

最终岛屿的数量就是并查集中连通分量的数目。

下面的动画展示了整个算法。

class 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) {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]);}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]) {swap(rootx, rooty);}parent[rooty] = rootx;if (rank[rootx] == rank[rooty]) rank[rootx] += 1;--count;}}int getCount() const {return count;}private:vector<int> parent;vector<int> 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();}
};

本文标签： 979

版权声明：本文标题：979 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732352096h1533377.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。