金华建设技工学校网站,商业网站的后缀,职业技术学院网站建设项目,软文写作发布文章目录1. 题目2. 解题1. 题目
给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组A. 初始二维矩阵全0. 二元数组A内的k个元素代表k次操作, 设第 i 个元素为 (A[i].x, A[i].y), 表示把二维矩阵中下标为A[i].x行A[i].y列的元素由海洋变为岛屿. 问在…
文章目录1. 题目2. 解题1. 题目
给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组A. 初始二维矩阵全0. 二元数组A内的k个元素代表k次操作, 设第 i 个元素为 (A[i].x, A[i].y), 表示把二维矩阵中下标为A[i].x行A[i].y列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. 你需要返回一个大小为k的数组.
样例 1:
输入: n 4, m 5,
A [[1,1],[0,1],[3,3],[3,4]]
输出: [1,1,2,2]
解释:
0. 00000000000000000000
1. 00000010000000000000
2. 01000010000000000000
3. 01000010000000000010
4. 01000010000000000011样例 2:
输入: n 3, m 3,
A [[0,0],[0,1],[2,2],[2,1]]
输出: [1,1,2,2]
注意事项
设定0表示海洋, 1代表岛屿, 并且上下左右相邻的1为同一个岛屿.https://www.lintcode.com/problem/number-of-islands-ii/description
2. 解题
并查集求解连通分量个数
/*** Definition for a point.* struct Point {* int x;* int y;* Point() : x(0), y(0) {}* Point(int a, int b) : x(a), y(b) {}* };*/class Solution {
public:/*** param n: An integer* param m: An integer* param operators: an array of point* return: an integer array*/vectorint f;int island 0;void merge(int a, int b){int fa find(a), fb find(b);if(fa ! fb){island--;f[fa] fb;}}int find(int a){if(a f[a]) return a;return f[a] find(f[a]);}vectorint numIslands2(int n, int m, vectorPoint operators) {// write your code heref.resize(n*m);for(int i 0; i m*n; i)f[i] i;unordered_setint landmark;//保存陆地压缩为一维vectorvectorint dir {{1,0},{0,1},{-1,0},{0,-1}};vectorint ans(operators.size());for(int i 0; i operators.size(); i){int x operators[i].x;int y operators[i].y;int idx m*x y;if(!landmark.count(idx)){ //新的陆地landmark.insert(idx);island;for(int k 0; k 4; k){ //周围的地方int nx xdir[k][0];int ny ydir[k][1];int nidx m*nxny;if(nx0 nx n ny0 ny m landmark.count(nidx)){ // 新陆地的四周在界内且是陆地merge(idx, nidx);// 合并}}}ans[i] island;}return ans;}
};853 ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
