Leetcode 305. Number of Islands II (python)

题目：

解法：hashmap

这道题是number of islands的follow up，关于number of islands见另外一篇博客。
这道题目的难点在于，当加入一个新的1的时候，岛的数量的变化需要分情况讨论增加或者减少或者不变，有如下几种情况：1. 新的点自成一个岛，那么岛的总数加1 2. 新的点与一个原有的岛相连，那么总数不变 3. 新的点与原来的两个，三个或者四个岛相连，岛的总数会相应的减少

解题思路如下：

• 建立一个hashmap，大小与grid map相同，每个1的位置对应岛的id，如果是连在一起的1，那么对应相同id，否则对应不同id
• 遍历每个位置，查看这个位置的四个邻接位置是否原本有岛
• 如果四个邻接位置原本都没有岛，那么当前位置自成一个岛，岛的总数加1并且为这个岛赋予新的id
• 如果邻接位置与一个原有的岛相连，那么岛的总数不变，将当前位置赋予相连的岛的id
• 如果邻接位置与两个，三个或者四个岛相连，那么岛的总数会相应的减少。这边需要将相连的这几个岛合并为这几个岛中任意的一个id，因为他们现在是一个岛了。同时也要将当前的位置赋予这个id

class Solution:def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:island_map = {
    }dirs = [[0,1],[0,-1],[-1,0],[1,0]]ans = []count = 0island_id = 0for pos in positions:if (pos[0],pos[1]) in island_map:ans.append(count)continueconnected_island = set()for d in dirs:x = pos[0]+d[0]y = pos[1]+d[1]if 0<=x<m and 0<=y<n and (x,y) in island_map:connected_island.add(island_map[(x,y)])if len(connected_island) == 0:island_map[(pos[0],pos[1])] = island_idisland_id += 1count += 1elif len(connected_island) == 1:for _id in connected_island:island_map[(pos[0],pos[1])] = _idelse:for _id in connected_island:new_id = _idbreakfor k,v in island_map.items():if v in connected_island:island_map[k] = new_idisland_map[(pos[0],pos[1])] = new_idcount = count-len(connected_island)+1#island_id += 1ans.append(count)return ans

解法2：unionfind

class UnionFind():def __init__(self):self.parent = {
    }self.count = 0def find(self,p):while p != self.parent[p]:p = self.parent[p]return pdef add_island(self,pos):if pos not in self.parent:self.parent[pos] = posself.count += 1def union(self,p,q):rootp = self.find(p)rootq = self.find(q)if rootp != rootq:self.parent[rootp] = self.parent[rootq]self.count -= 1class Solution:def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:uf = UnionFind()ans = []for (r,c) in positions:uf.add_island((r,c))for neigh in [(r-1,c),(r+1,c),(r,c+1),(r,c-1)]:if neigh in uf.parent:uf.union((r,c),neigh)ans.append(uf.count)return ans

c++版本

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class UF{
    
public:unordered_map<int,int> parent;int cnt = 0;int find(int p){
    while(parent[p] != p){
    p = parent[p];}return p;}void add_island(int p){
    if(!parent.count(p)){
    parent[p] = p;cnt++;}}int encode(int r,int c,int m){
    return r*m + c;}void union_(int p,int q){
    if(find(p) == find(q)) return;parent[find(p)] = find(q);cnt--;}};int main()
{
    vector<vector<int>> edges = {
    {
    0,0},{
    0,1},{
    1,2},{
    2,1}};int m = 3;int n = 3;UF uf;vector<int> ans;vector<vector<int>> dirs{
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};for(auto& edge : edges){
    int r = edge[0];int c = edge[1];int node = uf.encode(r,c,m);uf.add_island(node);for(auto& d : dirs){
    int neigh = uf.encode(r+d[0],c+d[1],m);if(uf.parent.count(neigh)){
    uf.union_(node,neigh);}}ans.push_back(uf.cnt);}for(auto& cnt : ans) cout << cnt << endl;return 0;
}

二刷

用vector表示这个parent，比较熟悉的形式

/******************************************************************************Online C++ Compiler.Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it.*******************************************************************************/#include <iostream>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>using namespace std;
class UF{
    int m;int n;public:vector<int> root;UF(int d1,int d2){
    m = d1;n = d2;for(int i=0;i<d1*d2;i++){
    root.push_back(-1);}}int count = 0;void add_island(int p){
    if(root[p] == -1){
    root[p] = p;count++;}}int find(int p){
    while(p!=root[p]){
    p = root[p];}return p;}void union_(int p,int q){
    if(find(p) != find(q)){
    root[find(p)] = find(q);count--;}}int encode(int i,int j){
    return i * n + j;}
};int main()
{
    vector<vector<int>> edges = {
    {
    0,0},{
    0,1},{
    1,2},{
    2,1}};int m = 3;int n = 3;//vector<int> root(m*n,-1);UF uf(m,n);vector<int> ans;vector<vector<int>> dirs{
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};for(auto& edge : edges){
    int node = uf.encode(edge[0],edge[1]);// cout << node << endl;uf.add_island(node);for(auto& d : dirs){
    int x = edge[0]+d[0];int y = edge[1]+d[1];if(x < 0 || y < 0 || x >= m || y >= n) continue;int neigh = uf.encode(edge[0]+d[0],edge[1]+d[1]);if(uf.root[neigh] != -1){
    uf.union_(node,neigh);}}ans.push_back(uf.count);}for(auto& cnt : ans) cout << cnt << endl;return 0;
}