网站建设接单源码,柳州论坛网站建设,免费下载ppt模板的网站有哪些,公司建设网站能提升什么竞争力思路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
明天继续更啦~
前序中序遍历二叉树
并查集做该道题
bfs的python写法
