Problem:
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:
- Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
- Output: [1,1,2,3]
- Explanation:
- 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
- Follow up:
- Can you do it in time complexity O(k log mn), where k is the length of the positions?
- Note:
You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.
- Solution:
经典的 Union Find 问题, 对于 Union 和 Find 函数, 我在 Union Find 算法总结 https://www.cnblogs.com/haoweizh/p/10179249.html 里已经讲述了基本原理, 在此不加赘述. 这道题的难点在于当加入一个 1 之后, 它可能将其上下左右四个方向的块连成一个整体, 比如
- 0 1 0 0 1 0
- 1 0 1 -> 1 1 1
- 0 1 0 0 1 0
这种情况下块的数量由 4 变为 1. 我们发现, 若中心位置的上下左右都为 0, 则块的数量加 1, 而当中心位置依次与上下左右四个块做四次 Union 操作, 而每一次 Union 操作都会将块的数量减少 1. 因此 1 = (4+1)-1-1-1-1 得到 Union 后的块数. 这里要注意一种特殊情况:
- 1 1 0 0 1 0
- 1 0 1 -> 1 1 1
- 0 1 0 0 1 0
即中心位置上面的 1 和左面的 1 其实属于同一个块, 所以当中心的 1 和左侧的 1 进行 Union 操作之后, 左侧的 1 和中心的 1 以及上面的 1 有着相同的根节点, 因此在中心的 1 和上面的 1 进行 Union 操作时不需要将块的数量减 1. 在这部分代码中, 我将 Union 函数设置了一个返回值, 用于判断两个块是否有共同的根节点 (不设返回值其实也可以, 我认为这样写代码更优雅).
- Code:
- class Solution {
- public:
- int Find(vector<int> &parent,int target){
- if(parent[target] == target)
- return target;
- return Find(parent,parent[target]);
- }
- bool Union(vector<int> &parent,vector<int> &rank,int first,int second){
- int px = Find(parent,first);
- int py = Find(parent,second);
- if(px == py) return false;
- if(rank[px]> rank[py]) parent[py] = px;
- else if(rank[py]> rank[px]) parent[px] = py;
- else{
- parent[py] = px;
- rank[px]++;
- }
- return true;
- }
- vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
- vector<int> result;
- vector<int> parent(m*n,0);
- vector<int> rank(m*n,0);
- vector<bool> visited(m*n,false);
- int count = 0;
- for(int i = 0;i != m;++i){
- for(int j = 0;j != n;++j){
- parent[i*n+j] = i*n+j;
- }
- }
- for(int i = 0;i != positions.size();++i){
- int x = positions[i].first;
- int y = positions[i].second;
- int index = x*n+y;
- visited[index] = true;
- count++;
- if(x-1>= 0 && visited[index-n] && Union(parent,rank,index,index-n))
- count--;
- if(x+1 <m && visited[index+n] && Union(parent,rank,index,index+n))
- count--;
- if(y-1>= 0 && visited[index-1] && Union(parent,rank,index,index-1))
- count--;
- if(y+1 < n && visited[index+1] && Union(parent,rank,index,index+1))
- count--;
- result.push_back(count);
- }
- return result;
- }
- };
来源: http://www.bubuko.com/infodetail-2898892.html