前言
中等 √ 做得我元气大伤,超级naive方法,新开辟一个数组存岛屿编号,一个数组存岛屿上的点。
题目
给你一个由 '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则进行判断,左上都没岛屿,新开辟一个岛;左边和上边任意一边有岛屿或者为相同岛屿,加入该岛;左边和上边都有岛屿且不是同一个岛,合并两岛并加入该岛,具体做法为把一个岛的点全部接到另一个岛上,更新island和index,注意此时原本的island的点为空。最后遍历island,不为空的岛的数量即为解集。
我的题解
class Solution {
public:int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0; int m = grid.size();int n = grid[0].size();vector<vector<pair<int, int>>> island;vector<vector<int>> index(m, vector<int>(n, -1));int count = 0;for (int i = 0; i < grid.size(); i++){for (int j = 0; j < grid[0].size(); j++){int left = -1, top = -1;if (grid[i][j] == '1'){if (i > 0)top = index[i-1][j];if (j > 0)left = index[i][j-1];//左上都没岛屿,新建一岛//左上一边有岛屿或左上岛屿相同,加入该岛//左上岛屿不同,合并两岛if (left == -1 && top == -1){//更新inland,indexisland.push_back({{i, j}});index[i][j] = count;count++;}else{if (top == -1 || left == -1 || top == left){int temp = max(left, top);island[temp].push_back({i,j});index[i][j] = temp;}else{//合并两岛, left移到上边int temp1 = min(top, left);int temp2 = max(top, left);island[temp1].push_back({i,j});index[i][j] = temp1;for (int i = 0; i < island[temp2].size(); i++){pair<int, int> temp = island[temp2][i];index[temp.first][temp.second] = temp1; }island[temp1].insert(island[temp1].end(), island[temp2].begin(), island[temp2].end());island[temp2] = {}; }}}}}int ans = 0;for (int i = 0; i < island.size(); i++){if (!island[i].empty())ans++;}return ans;}
};
官方题解
深度优先搜索
我们可以将二维网格看成一个无向图,竖直或水平相邻的 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;}
};
广度优先搜索
同样地,我们也可以使用广度优先搜索代替深度优先搜索。
为了求出岛屿的数量,我们可以扫描整个二维网格。如果一个位置为 1,则将其加入队列,开始进行广度优先搜索。在广度优先搜索的过程中,每个搜索到的 1 都会被重新标记为 0。直到队列为空,搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。
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;}
};
并查集
同样地,我们也可以使用并查集代替搜索。
为了求出岛屿的数量,我们可以扫描整个二维网格。如果一个位置为 1,则将其与相邻四个方向上的 1 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
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();}
};
知识点
开辟静态数组:vector<vector<int>> index(m, vector<int>(n, -1));
数组置空:island[temp2] = {};
心得
这个题目做了好久....重新做图的题已经忘了一般怎么解了,只会当成一个普通数组,在好多个测试案例报错之后不断debug,终于完成了我的“笨”方法,感觉有点类似并集法且不会改变图原有的结构和内容,不过题解的并集法太复杂了,故只学习一下dfs和bfs。核心是顺着陆地向上下左右四个方向搜陆地,搜到的陆地标为0,这样在重新进行搜索的时候就是一块“新大陆”,即题解。虽然这个题目没想到标准解法,但我的解法也是可行而且时空复杂度相同,并且实现了额外的功能:点->岛,岛->点。所以不要气馁,积累积累,思考才是最可贵的!!噢,另外数组/容器的用法学习要系统化一下了,这么基础的用法不能老是问ai~