[LeetCode] Number of Islands II

简介: Problem Description: A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land.

Problem Description:

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]


This problem requires a classic data structure called UnionFind. Take some efforts to learn it at first, like using this Princeton's notes offered by peisi. This note is very nicely written. Take some patinece to read through it and you will get a tool that is also helpful in the future :-) 

The C++ code is as follows, taking peisi's Java code as an example.

 1 class UnionFind2D {
 2 public:
 3     UnionFind2D(int m, int n) {
 4         for (int i = 0; i < m * n; i++) ids.push_back(-1);
 5         for (int i = 0; i < m * n; i++) szs.push_back(1);
 6         M = m, N = n, cnt = 0;
 7     }
 8     int index(int x, int y) {
 9         return x * N + y;
10     }
11     int size(void) {
12         return cnt;
13     }
14     int id(int x, int y) {
15         if (x >= 0 && x < M && y >= 0 && y < N)
16             return ids[index(x, y)];
17         return -1;
18     }
19     int add(int x, int y) {
20         int idx = index(x, y);
21         ids[idx] = idx;
22         szs[idx] = 1;
23         cnt++;
24         return idx;
25     }
26     int root(int i) {
27         for (; i != ids[i]; i = ids[i])
28             ids[i] = ids[ids[i]];
29         return i;
30     }
31     bool find(int p, int q) {
32         return root(p) == root(q);
33     }
34     void unite(int p, int q) {
35         int i = root(p), j = root(q);
36         if (szs[i] > szs[j]) swap(i, j);
37         ids[i] = j;
38         szs[j] += szs[i];
39         cnt--;
40     }
41 private:
42     vector<int> ids, szs;
43     int M, N, cnt;
44 };
45 
46 class Solution {
47 public:
48     vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
49         UnionFind2D islands(m, n);
50         vector<pair<int, int>> dirs = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
51         vector<int> ans;
52         for (auto& pos : positions) {
53             int x = pos.first, y = pos.second;
54             int p = islands.add(x, y);
55             for (auto& d : dirs) {
56                 int q = islands.id(x + d.first, y + d.second);
57                 if (q >= 0 && !islands.find(p, q))
58                     islands.unite(p, q);
59             }
60             ans.push_back(islands.size());
61         }
62         return ans;
63     }
64 };

 

目录
相关文章
|
11月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
92 1
|
4月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
5月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
40 0
|
11月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
37 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
|
16天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
47 6