200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

输出：1
示例 2：
输入：

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：3

具体题目链接

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        lenght_r,lenght_c,nums=len(grid),len(grid[0]),0
        for i in range(lenght_r):
            for j in range(lenght_c):
                if grid[i][j]=='1':
                    nums+=1
                    self.dfs(i,j,lenght_r,lenght_c,grid)
        return nums
    def dfs(self,i,j,lenght_r,lenght_c,grid):
        grid[i][j]=0
        xy=[(i-1,j),(i,j-1),(i,j+1),(i+1,j)]
        for x,y in xy:
            if 0<=x<lenght_r and 0<=y<lenght_c and grid[x][y]=='1':
                self.dfs(x,y,lenght_r,lenght_c,grid)

思路：深度优先搜索

class findjoin:
    def __init__(self,lenR,lenC,grid) -> None:
        self.count=0
        self.pre=[-1]*lenR*lenC
        self.rank=[0]*lenR*lenC
        for x in range(lenR):
            for y in range(lenC):
                if grid[x][y]=='1':
                    self.count+=1
                    self.pre[x*lenC+y]=x*lenC+y

    def find(self,x)->int:
        if self.pre[x]!=x:
            self.pre[x]=self.find(self.pre[x])
        return self.pre[x]
    def join(self,x,y):
        fx,fy=self.find(x),self.find(y)
        if fx!=fy:
            if self.rank[fx]<self.rank[fy]:
                fx,fy=fy,fx
            self.pre[fy]=fx
            self.count-=1
            if self.rank[fx]==self.rank[fy]:
                self.rank[fx]+=1
    def getcount(self):
        return self.count

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        lenR,lenC=len(grid),len(grid[0])
        fd=findjoin(lenR,lenC,grid)
        for x in range(lenR):
            for y in range(lenC):
                if grid[x][y]=='1':
                    grid[x][y]=='0'
                    for x1,y1 in [(x,y-1),(x+1,y)]:
                        if 0<=x1<lenR and  0<=y1<lenC and grid[x1][y1]=='1':
                            fd.join(x*lenC+y,x1*lenC+y1)
        return fd.getcount()

思路：查并集，这是一种新的思路。断断续续看了几天才理解。看的这个文章链接进行基础学习，之后又看的文章链接学习。查并集共两个模块，一是find，为了寻找根节点，而是join，为了合并两个节点。

GO

func numIslands(grid [][]byte) int {
    lenR,lenC:=len(grid),len(grid[0])
    x_y:=[][]int{{0,1},{1,0}}
    count:=0
    pre:=make([]int,lenR*lenC)
    rank:=make([]int,lenR*lenC)
    for i:=range pre{
        if grid[i/lenC][i%lenC]=='1'{
            count++
            pre[i]=i
        }else{
            pre[i]=-1
        }
        rank[i]=0
    }
    var find func(x int) int
    find=func(x int) int{
        if pre[x]!=x{
            pre[x]=find(pre[x])
        }
        return pre[x]
    }
    join:=func(x,y int){
        fx,fy:=find(x),find(y)
        if fx!=fy{
            if rank[fx]<rank[fy]{
                fx,fy=fy,fx
            } 
            pre[fy]=fx
            count--
            if rank[fx]==rank[fy]{
                rank[fx]++
            }     
        }
    }
    for x:=0; x<lenR;x++{
        for y:=0;y<lenC;y++{
            if grid[x][y]=='1'{
                grid[x][y]='0'
                for _,xy:=range x_y{
                    x1,y1:=x+xy[0],y+xy[1]
                    if 0<=x1&&x1<lenR &&  0<=y1&&y1<lenC && grid[x1][y1]=='1'{
                        join(x*lenC+y,x1*lenC+y1)
                    }
                }
            }
        }
    }
    return count
}

思路：并查集,同python

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnectedi = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnectedi = 0 表示二者不直接相连。返回矩阵中 省份 的数量。
示例详细看下方链接
具体题目链接

Python

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i):
            for j in range(length):
                if isConnected[i][j] == 1 and j not in visited:#如果为1则证明被联通，并且当没在已记录城市内
                    visited.add(j)#增加已记录城市。
                    dfs(j)
        length=len(isConnected)#获取长度
        visited=set()#集合，记录已经被链接的城市
        circles = 0#记录省份
        for i in range(length):
            if i not in visited:
                dfs(i)
                circles+=1
        return circles

思路：深度优先搜索，先创建visited，用来记录已经被联通的城市。

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        def union(index1, index2):
            parent[find(index1)] = find(index2)
        provinces = len(isConnected)
        parent = list(range(provinces))
        for i in range(provinces):
            for j in range(i + 1, provinces):
                if isConnected[i][j] == 1:
                    union(i, j)
        circles = sum(parent[i] == i for i in range(provinces))
        return circles

思路：查并集，标准查并集形式。

GO

func findCircleNum(isConnected [][]int) int {
    provinces:=len(isConnected)
    parent:=make([]int, provinces)
    for i:=range parent{
        parent[i]=i
    }
    var find func(int) int
    find=func (index int) int{
        if parent[index]!=index{
            parent[index]=find(parent[index])
        }
        return parent[index]
    }
    union:=func (index1,index2 int) {
        parent[find(index1)]=find(index2)
    }
    for i,row:=range isConnected{
        for j:=i+1;j<provinces;j++{
            if row[j]==1{
                union(i,j)
            }
        }
    }
    circles:=0
    for i,p:=range parent{
        if i==p{
            circles++
        }
    }
    return circles
}

思路：查并集，思路同python

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2dqha69nsxa8s