网站权重不够高 导致,网站开发模块学些什么,wordpress自定义模板下载,建设一个班级网站的具体步骤LeetCode 695- 岛屿的最大面积
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给你一个有 n 个节点的 有向无环图#xff08;DAG#xff09;#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出…LeetCode 695- 岛屿的最大面积
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个有 n 个节点的 有向无环图DAG请你找出所有从节点 0 到节点 n-1 的路径并输出不要求按特定顺序
graph[i] 是一个从节点 i 可以访问的所有节点的列表即从节点 i 到节点 graph[i][j]存在一条有向边。
解题思路
首先确定递归函数的参数返回值。本题要路径我们直接设置两个全局变量result和path这样可以不用写太多参数传递。返回值就是void参数需要图和一个start。start来标记我们当前走到了哪个节点下次从这个节点开始走的。确定终止条件本题是到特定点的路径所以path的最后一个数值为特定节点就终止。即start graph.size()-1
单层处理逻辑每次将当前节点中能通向的路径都走一遍也就是将其全部都递归一遍。
class Solution {
public:vectorint path;vectorvectorint result;void traversal(vectorvectorint graph,int start){if(start graph.size()-1){result.push_back(path);//return ;}for(int i0;igraph[start].size();i){path.push_back(graph[start][i]);traversal(graph,graph[start][i]);path.pop_back();}}vectorvectorint allPathsSourceTarget(vectorvectorint graph) {path.push_back(0);traversal(graph,0);return result;}
}; 总结
递归的应用
LeetCode 200- 岛屿数量
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
解题思路
思路一深度优先遍历
首先确定递归函数的参数返回值。本题不需要这些。确定终止条件本题按我们的逻辑先进入循环再判断是否应该终止那么终止条件就是当超出网格范围就终止。
单层处理逻辑每次我们将当前节点的岛屿的值设置为0模拟为被淹没并且去淹没当前节点的上下左右相邻的节点。为1的节点为陆地状态。 class Solution {
public:int numIslands(vectorvectorchar grid) {int islandNum 0;for (int i 0; i grid.size(); i) {for (int j 0; j grid[0].size(); j) {//如果是陆地那就进行深度优先遍历不断淹没陆地if (grid[i][j] 1) {dfs(grid, i, j);islandNum;}}}return islandNum;}
public:void dfs(vectorvectorchar grid, int i, int j) {//这里是先进递归后判断是否符合条件不符合直接return符合才会向更深处递归。if (i 0 || j 0 || i grid.size() || j grid[0].size() || grid[i][j] ! 1) return;grid[i][j] 0;dfs(grid, i 1, j);dfs(grid, i - 1, j);dfs(grid, i, j 1);dfs(grid, i, j - 1);}
};
思路二广度优先遍历
用队列模拟广度优先首先入队第一个遇到的陆地然后遍历其上下左右的空间是陆地就入队且淹没非陆地就不操作不断进行直到全部变为海洋为止。
class Solution {
public:int dir[4][2] {0,1,1,0,-1,0,0,-1};//定义四个方向的走向这个4x2的矩阵就是代表4个方向int numIslands(vectorvectorchar grid) {int res 0;int n grid.size(),m grid[0].size();for(int i0;in;i){for(int j0;jm;j){if(grid[i][j] 1){//当遇到陆地时进行广度优先遍历bfs(grid,i,j);//广度优先结束后说明刚刚淹没一片陆地resres ; //若下次还有陆地要淹则res会继续} }}return res;}void bfs(vectorvectorchar grid,int x,int y){queuepairint,int que;//队列模拟广度优先其中存储的是对组为xy坐标que.push({x,y});//首先压入传进来的岛屿的位置grid[x][y] 0;//将其淹没while(!que.empty()){//若队列不为空则一直循环pairint,int cur que.front();//取出头部的陆地坐标que.pop();int curx cur.first;//赋值给当前xy坐标int cury cur.second;//对四个方向进行遍历也就是对当前陆地的一周进行遍历如果有陆地那就入队。for(int i0;i4;i){int nextx curx dir[i][0];int nexty cury dir[i][1];//如果当前走的一步没有越界且是陆地则将其入队然后淹没。if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size() ||grid[nextx][nexty] ! 1) continue;que.push({nextx,nexty});grid[nextx][nexty] 0;}}}
};
总结
与其想符合条件的递归不如想不符合条件的返回高效又不易错。本题体现在与其去想怎么样进入递归不如想什么情况下进入递归了不符合条件直接返回。
