鲜花网网站开发的目标,网站域名的选择,云南网络公司网站建设,公司黄页企业名录在哪里查dfs思路#xff1a; 首先通过两层for循环遍历每一个点#xff0c;如果这个点为0或者2#xff08;这个2是什么呢#xff1f;是在遍历该点以及该点连成的这一片区域中#xff0c;因为通过深度优先搜索#xff0c;遍历该点就等于遍历这一片区域#xff0c;遍历这篇区域中的…
dfs思路 首先通过两层for循环遍历每一个点如果这个点为0或者2这个2是什么呢是在遍历该点以及该点连成的这一片区域中因为通过深度优先搜索遍历该点就等于遍历这一片区域遍历这篇区域中的点的同时将这些元素标记为2即代表这篇区域已经遍历过那么遍历下一个点。遇到一个新的区域则cnt。 那么怎么进行深度搜索呢即如果该点1那么将该点的上方、下方、左方、右方送入dfs。 dfs代码
C:
class Solution {
public:int p_m[4]{-1,1,0,0};int p_n[4]{0,0,-1,1};void dfs(vectorvectorchar grid,int i,int j,int m,int n){for(int k0;k4;k){int xip_m[k];int yjp_n[k];if(x0 xm y0 yn){if(grid[x][y]0||grid[x][y]2){continue;}else{grid[x][y]2;dfs(grid,x,y,m,n);}}}}int numIslands(vectorvectorchar grid) {int mgrid.size();int ngrid[0].size();//coutm nendl;int cnt0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]2||grid[i][j]0){continue;}else{dfs(grid,i,j,m,n);cnt;}}}return cnt;}
};
注意二维数组中求行数为
int mgrid.size();
求列数为
int ngrid[0].size();
python
class Solution:def dfs(self,grid:List[list[str]],i:int,j:int,m:int,n:int) - int:p_m[-1,1,0,0]p_n[0,0,-1,1]for k in range(4):xip_m[k]yjp_n[k]if x0 and xm and y0 and yn:if grid[x][y]0 or grid[x][y]2:continueelse:grid[x][y]2self.dfs(grid,x,y,m,n)def numIslands(self, grid: List[List[str]]) - int:mlen(grid)nlen(grid[0])cnt0for i in range(m):for j in range(n):if grid[i][j]2 or grid[i][j]0:continue;else:self.dfs(grid,i,j,m,n)cnt1return cnt
bfs思路 与dfs类似遍历每个元素时如果该元素的值为1那么将其入队列并且考虑其上下左右的元素如果周围元素值为1将其也入队列。遍历一个元素时如果该值为1那么代表访问了一个新的区域则cnt。 代码
C
class Solution {
public:dequepairint,int q;int p_x[4]{-1,1,0,0};int p_y[4]{0,0,1,-1};int numIslands(vectorvectorchar grid) {int cnt0;int mgrid.size();int ngrid[0].size();for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]0||grid[i][j]2){continue;}else{cnt;}q.push_back({i,j});while(!q.empty()){pairint,int tempq.front();q.pop_front();int temp_xtemp.first;int temp_ytemp.second;if(grid[temp_x][temp_y]0||grid[temp_x][temp_y]2){continue;}else{grid[temp_x][temp_y]2;for(int k0;k4;k){int xtemp_xp_x[k];int ytemp_yp_y[k];if(x0 xm y0 yn){if(grid[x][y]0||grid[x][y]2){continue;}else{q.push_back({x,y});}}}}}}}return cnt;}
};
明显可以看到bfs要比dfs慢的多。 python
class Solution:def numIslands(self, grid: List[List[str]]) - int:qdeque()p_x[-1,1,0,0]p_y[0,0,1,-1]cnt0mlen(grid)nlen(grid[0])for i in range(m):for j in range(n):if grid[i][j]0 or grid[i][j]2:continueelse:cnt1q.append((i,j))while q:tempq[0]q.popleft()temp_xtemp[0]temp_ytemp[1]if grid[temp_x][temp_y]0 or grid[temp_x][temp_y]2:continueelse:grid[temp_x][temp_y]2for k in range(4):xtemp_xp_x[k]ytemp_yp_y[k]if x0 and xm and y0 and yn:if grid[x][y]0 or grid[x][y]2:continueelse:q.append((x,y))return cnt
注意C中的pairint,int用python中的tuple来代替
q.append((i,j))
同时记得添加from collections import deque
并查集思路 遍历所有元素如果该元素为‘0’则跳过如果该元素为‘1’cnt岛屿数后面再依次向下减同时为其分配一个Father结点值为其本身但是本身是i,j该怎么存到Father数组中呢用二维数组转换成一维数组的方法即将i,j转换为i*nj【相当于以行优先看是第几个元素】。接下来依次判断上下左右值如果为1就和自己合并。这里分为真合并和假合并假合并就是这两个值原来就合并过。如果是真合并则进行cnt--的操作。 并查集代码
C
class Solution {
public:int p_x[4]{-1,1,0,0};int p_y[4]{0,0,-1,1};int cnt0;int find(vectorint Father,int x){if(Father[x]x){return x;}Father[x]find(Father,Father[x]);return Father[x];}void Union(vectorint Father,int x,int y){int Fxfind(Father,x);int Fyfind(Father,y);if(FxFy){return;}Father[Fy]Fx;cnt--;}int numIslands(vectorvectorchar grid) {int mgrid.size();int ngrid[0].size();vectorint Father(m*n,0);//初始化Father数组for(int i0;im;i){for(int j0;jn;j){int tempn*ij;if(grid[i][j]1){Father[temp]temp;cnt;}else{Father[temp]-1;}}}//Unionfor(int i0;im;i){for(int j0;jn;j){if(grid[i][j]0){continue;}for(int k0;k4;k){int xip_x[k];int yjp_y[k];if(x0 xm y0 yn){if(grid[x][y]0){continue;}else{int ai*nj;int bx*ny;Union(Father,a,b);}}}}}return cnt;}
};
Python class Solution:def find(self,Father:List[int],x:int) - int:if Father[x]x:return xFather[x]self.find(Father,Father[x])return Father[x]def Union(self,Father:List[int],x:int,y:int,cnt:int) -int:Fxself.find(Father,x)Fyself.find(Father,y)if FxFy:return cntFather[Fy]Fxcnt-1return cntdef numIslands(self, grid: List[List[str]]) - int:p_x[-1,1,0,0]p_y[0,0,-1,1]mlen(grid)nlen(grid[0])Father[0]*(m*n)cnt0for i in range(m):for j in range(n):tempn*ijif grid[i][j]1:Father[temp]tempcnt1else:Father[temp]-1for i in range(m):for j in range(n):if grid[i][j]0:continuefor k in range(4):xip_x[k]yjp_y[k]if x0 and xm and y0 and yn:if grid[x][y]0:continueelse:ai*njbx*nycntself.Union(Father,a,b,cnt)return cnt
注意类中函数第一个参数为self
