二级网站建设规范,如何做wordpress文章页,wish网站应该怎么做,h5网址文章目录1. 题目2. 解题2.1 超时解2.1 改进计算方法1. 题目
假设你设计一个游戏#xff0c;用一个 m 行 n 列的 2D 网格来存储你的游戏地图。
起始的时候#xff0c;每个格子的地形都被默认标记为「水」。 我们可以通过使用 addLand 进行操作#xff0c;将位置 (row, col)…
文章目录1. 题目2. 解题2.1 超时解2.1 改进计算方法1. 题目
假设你设计一个游戏用一个 m 行 n 列的 2D 网格来存储你的游戏地图。
起始的时候每个格子的地形都被默认标记为「水」。 我们可以通过使用 addLand 进行操作将位置 (row, col) 的「水」变成「陆地」。
你将会被给定一个列表来记录所有需要被操作的位置然后你需要返回计算出来 每次 addLand 操作后岛屿的数量。
注意一个岛的定义是被「水」包围的「陆地」通过水平方向或者垂直方向上相邻的陆地连接而成。 你可以假设地图网格的四边均被无边无际的「水」所包围。
请仔细阅读下方示例与解析更加深入了解岛屿的判定。
示例:
输入: m 3, n 3, positions [[0,0], [0,1], [1,2], [2,1]]
输出: [1,1,2,3]
解析:
起初二维网格 grid 被全部注入「水」。0 代表「水」1 代表「陆地」
0 0 0
0 0 0
0 0 0操作 #1addLand(0, 0) 将 grid[0][0] 的水变为陆地。
1 0 0
0 0 0 Number of islands 1
0 0 0操作 #2addLand(0, 1) 将 grid[0][1] 的水变为陆地。
1 1 0
0 0 0 岛屿的数量为 1
0 0 0操作 #3addLand(1, 2) 将 grid[1][2] 的水变为陆地。
1 1 0
0 0 1 岛屿的数量为 2
0 0 0操作 #4addLand(2, 1) 将 grid[2][1] 的水变为陆地。
1 1 0
0 0 1 岛屿的数量为 3
0 1 0拓展
你是否能在 O(k log mn) 的时间复杂度程度内完成每次的计算
k 表示 positions 的长度来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-islands-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考数据结构并查集Disjoint-Set
2.1 超时解
125 / 162 个通过测试用例
将矩阵的每个位置看成并查集中的一个点每次加入一个岛屿把四周是1的点合并掉计算集团个数时间复杂度 O(kmn)O(kmn)O(kmn)
class dsu
{
public:vectorint f;dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a);int fb find(b);f[fa] fb;}int find(int a){int origin a;while(a ! f[a])a f[a];return f[origin] a;}int countUni(vectorvectorint grid){int count 0, x, y, n grid[0].size();for(int i 0; i f.size(); i){ x i/n, y i-x*n;if(i find(i) grid[x][y]1)count;}return count;}
};
class Solution {
public:vectorint numIslands2(int m, int n, vectorvectorint positions) {int N m*n, pos, x, y;vectorvectorint grid(m,vectorint(n,0));dsu u(N);vectorint ans(positions.size());vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};for(int i 0, k; i positions.size(); i){grid[positions[i][0]][positions[i][1]] 1;//标记为岛屿pos positions[i][0]*npositions[i][1];//对应并查集中的位置for(k 0; k 4; k){x positions[i][0] dir[k][0];y positions[i][1] dir[k][1];//周围坐标x,yif(x0 xm y0 yn grid[x][y]1)u.merge(pos, x*ny);//合并}ans[i] u.countUni(grid);}return ans;}
};2.1 改进计算方法
并查集merge 函数返回是否被合并了合并了数量就减1注意有重复岛屿不能算
class dsu
{
public:vectorint f;dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}bool merge(int a, int b){int fa find(a);int fb find(b);if(fa ! fb){f[fa] fb;return true;}return false;//返回是否被合并了}int find(int a){int origin a;while(a ! f[a])a f[a];return f[origin] a;}
};
class Solution {
public:vectorint numIslands2(int m, int n, vectorvectorint positions) {int N m*n, pos, x, y;vectorvectorint grid(m,vectorint(n,0));dsu u(N);vectorint ans(positions.size());vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};unordered_setint s;//有重复的岛屿for(int i 0, k; i positions.size(); i){ans[i] (i0 ? ans[i-1] : 0 )1;//先把这个岛屿算作孤立1grid[positions[i][0]][positions[i][1]] 1;//标记为岛屿pos positions[i][0]*npositions[i][1];//对应并查集中的位置if(s.count(pos))//有该岛屿了重复添加{ans[i]--;continue;}s.insert(pos);for(k 0; k 4; k){x positions[i][0] dir[k][0];y positions[i][1] dir[k][1];//周围坐标x,yif(x0 xm y0 yn grid[x][y]1){if(u.merge(pos, x*ny))//合并了ans[i]--;//减1}}}return ans;}
};156 ms 34.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
