LeetCode-算法- 广度和深度优先搜索-第20天
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
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021年08月26日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录