当前位置: 首页> 教育> 就业 > 无锡网站制作供应_php做一个网站_seo与sem的关系_央视新闻的新闻

无锡网站制作供应_php做一个网站_seo与sem的关系_央视新闻的新闻

时间:2025/7/11 0:57:55来源:https://blog.csdn.net/hahashrimp/article/details/147191218 浏览次数:1次
无锡网站制作供应_php做一个网站_seo与sem的关系_央视新闻的新闻

前言

中等 √ 做得我元气大伤,超级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~

关键字:无锡网站制作供应_php做一个网站_seo与sem的关系_央视新闻的新闻

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: