皖icp网站建设,小型手机网站建设哪家好,商业网站制作价格,潍坊百度关键词优化LeetCode 130- 被围绕的区域
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给你一个 m x n 的矩阵 board #xff0c;由若干字符 X 和 O #xff0c;找到所有被 X 围绕的区域#xff0c;并将这些区域…LeetCode 130- 被围绕的区域
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个 m x n 的矩阵 board 由若干字符 X 和 O 找到所有被 X 围绕的区域并将这些区域里所有的 O 用 X 填充。
解题思路思路一是自己的思路思路二题解思路不过用两种遍历方式写出来
思路一深度优先遍历
我的思路是开辟一个二维数组存储二元组来记录那些下标首先是一个一维数组每次记录我们当前遍历岛屿的下标当被环绕的时候压入到二维数组中否则直接清空。类似将所有岛屿都淹没然后再看哪些岛屿没被包围再还原成陆地。
首先确定递归函数的参数返回值。覆盖那些被环绕的区域我们直接设置两个全局变量vec存储所有需要还原的海洋和tmp存储当前我们遍历的这片岛屿的下标flag表示是否被包围这样可以不用写太多参数传递。返回值就是void参数需要图和一个x和y来记录当前在哪个岛屿。下次从这个岛屿开始走的。确定终止条件本题按我们的逻辑先进入循环再判断是否应该终止那么终止条件就是当超出网格范围(这里还需要把flag 设置为false表示没被包围) 或 该岛屿已经是海洋 就终止。单层处理逻辑每次将当前岛屿淹没这里也就是设置为X然后将其下标压入tmp为什么有tmp是因为我们不知道当前的这片岛屿马上是否要恢复也就是变成O所以需要一个临时的当我们确定要恢复的时候就将其压入到vec中。
class Solution {
public:bool flag true; //表示是否被环绕只要相连的岛屿有一个在边界就不是被环绕的,被环绕就不用撤回修改vectorvectorpairint,int vec;//存所有岛屿下标其中全都是要变回O的vectorpairint,int tmp; //保存当前遍历这片岛屿的下标一会可能填充。void dfs(vectorvectorchar grid,int x,int y){if(x 0 || y 0 || x grid.size() || y grid[0].size()){flag false;//表示没有被环绕return ;}if(grid[x][y] X) return;tmp.push_back({x,y});//压入当前岛屿的下标grid[x][y] X;dfs(grid,x1,y);dfs(grid,x-1,y);dfs(grid,x,y1);dfs(grid,x,y-1);}void solve(vectorvectorchar grid) {int m grid.size(),n grid[0].size();for(int i0;im;i){for(int j0;jn;j){if(grid[i][j] O){dfs(grid,i,j);//当flag为false也就是岛屿没有被包围我们就将其压入vec中最后再还原if(flag false){vec.push_back(tmp);tmp.clear();//这里注意要把tmp清空了方便下次使用flag true;//flag再改为默认值}else{//这里不改flag是因为如果走这个分支那flag一定还是默认值truetmp.clear();}}}}//将未被包围的小岛屿还原为Ofor(int i0;ivec.size();i){for(int j0;jvec[i].size();j){grid[vec[i][j].first][vec[i][j].second] O;}}return ;}
};
思路二广度优先遍历
比较猛的一个思路本题我们可以看到只有和边界相连的O不会变其余的都得变成X那么我们可以将与边界相连的所有O全部变成一个特定符号如-这样其中所有的-都是与边界相连的马上会再变成O。而这个时候图中所有的O都是被包围的全都变为X即可。
class Solution {
public:int dir[4][2] {0,1,1,0,-1,0,0,-1};void bfs(vectorvectorchar grid,int x,int y){queuepairint,int que;que.push({x,y});grid[x][y] -;//将与边界相连的全部变为-//广度优先遍历while(!que.empty()){pairint,int cur que.front();que.pop();for(int i0;i4;i){int nextx cur.first dir[i][0];int nexty cur.second dir[i][1];if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size() ||grid[nextx][nexty] ! O) continue;que.push({nextx,nexty});grid[nextx][nexty] -;}}}void solve(vectorvectorchar grid) {int row grid.size(),col grid[0].size();for(int i0;icol;i){//遍历第一行的所有列if(grid[0][i] O) bfs(grid,0,i);//遍历最后一行的所有列if(grid[row-1][i] O) bfs(grid,row-1,i);}for(int i0;irow;i){//遍历第一列的所有行if(grid[i][0] O) bfs(grid,i,0);//遍历最后一列的所有行if(grid[i][col-1] O) bfs(grid,i,col-1);}//这个时候图中所有-都是与边界相连的所有O都是被包围起来的。for(int i0;irow;i){for(int j0;jcol;j){//这俩式子顺序反了导致花了我半小时调试if(grid[i][j] O)grid[i][j] X;if(grid[i][j] -)grid[i][j] O;}}return ;}
};
总结
深搜和广搜的问题广搜里面写的那个思路很清奇还是得多看题目的提示可以减少一点时间和空间的损耗。
LeetCode 417- 太平洋大西洋水流问题
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述有一个 m × n 的矩形岛屿与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多如果相邻单元格的高度 小于或等于 当前单元格的高度雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 其中 result[i] [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
解题思路
首先明确本题题意意思就是雨水高的地方能往雨水低的地方流要我们求出能流向两大洋的点坐标。
思路一深度优先遍历
这题总体思路就是遍历边界点也就是能直接流进大洋的点再逆流遍历因为雨水往低处流我们逆流遍历就可以找到所有大于边界的雨水高度的点这些点就是可以直接流进大洋的点
首先确定递归函数的参数返回值。参数我们需要设置一个isvisited来表示这个点能不能走到其中一个大洋中去。还有xy坐标来表示当前遍历到的点的位置确定终止条件本题按我们的逻辑先进入循环再判断是否应该终止那么终止条件就是当超出网格范围 或 当前遍历的是海洋 就跳过。不过这里需要注意这道题目我们这里的逻辑是逆流而上所以下一次要去的节点的雨水高度 小于 我们当前节点的雨水高度的时候也直接跳过。
单层处理逻辑每次进入递归我们就将访问设置为true代表可以直接流进大洋。不过在处理遍历的时候有点麻烦需要注意m和n各表示的是什么别弄混了。
class Solution {
private:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向// 从低向高遍历注意这里visited是引用即可以改变传入的pacific和atlantic的值void dfs(vectorvectorint heights, vectorvectorbool visited, int x, int y) {if (visited[x][y]) return;visited[x][y] true;for (int i 0; i 4; i) { // 向四个方向遍历int nextx x dir[i][0];int nexty y dir[i][1];// 超过边界if (nextx 0 || nextx heights.size() || nexty 0 || nexty heights[0].size()) continue;// 高度不合适注意这里是从低向高判断if (heights[x][y] heights[nextx][nexty]) continue;dfs (heights, visited, nextx, nexty);}return;}
public:vectorvectorint pacificAtlantic(vectorvectorint heights) {vectorvectorint result;int n heights.size();int m heights[0].size(); // 这里不用担心空指针题目要求说了长宽都大于1// 记录从太平洋边出发可以遍历的节点vectorvectorbool pacific vectorvectorbool(n, vectorbool(m, false));// 记录从大西洋出发可以遍历的节点vectorvectorbool atlantic vectorvectorbool(n, vectorbool(m, false));// 从最上最下行的节点出发向高处遍历for (int i 0; i n; i) {dfs (heights, pacific, i, 0); // 遍历最上行接触太平洋dfs (heights, atlantic, i, m - 1); // 遍历最下行接触大西洋}// 从最左最右列的节点出发向高处遍历for (int j 0; j m; j) {dfs (heights, pacific, 0, j); // 遍历最左列接触太平洋dfs (heights, atlantic, n - 1, j); // 遍历最右列接触大西洋}for (int i 0; i n; i) {for (int j 0; j m; j) {// 如果这个节点从太平洋和大西洋出发都遍历过就是结果if (pacific[i][j] atlantic[i][j]) result.push_back({i, j});}}return result;}
};总结
逆流而上的操作主要是根据边界来想到了这个思路。
