网站建设评估体系,p2p网站建设框架,做推广软件,福田网站设计公司哪家好130. 被围绕的区域
leetcode链接#xff1a;题目链接 这题看起来很复杂#xff0c;其实跟之前找飞地和找边缘地区的是差不多的#xff0c;主要分三步#xff1a;
使用dfs将边缘的岛都找出来#xff0c;然后用A代替防止混淆#xff1b;再用dfs找中间不与任何岛相连的飞地…130. 被围绕的区域
leetcode链接题目链接 这题看起来很复杂其实跟之前找飞地和找边缘地区的是差不多的主要分三步
使用dfs将边缘的岛都找出来然后用A代替防止混淆再用dfs找中间不与任何岛相连的飞地最后把之前的A替换成O。
最终代码
class Solution {
public:void dfs(vectorvectorchar board, int i, int j, char ch){//找到o把其周围转化为chvectorint dir {0,-1,0,1,1,0,-1,0};if(i 0 || j 0 || i board.size() || j board[0].size()){return;}if(board[i][j] X || board[i][j] a){return;}board[i][j] ch;for(int idx 0; idx 4; idx){dfs(board, i dir[2 * idx], j dir[2 * idx 1],ch);}}void solve(vectorvectorchar board) {int m board.size();int n board[0].size();for(int i 0; i m; i){if(board[i][n - 1] O){dfs(board,i, n - 1, a);}if(board[i][0] O){dfs(board,i,0, a);}}for(int j 0; j n; j){if(board[0][j] O){dfs(board,0, j,a);}if(board[m - 1][j] O){dfs(board, m - 1, j,a);}}for(int i 0; i m; i){for(int j 0; j n;j){if(board[i][j] O){board[i][j] X;}if(board[i][j] a){board[i][j] O;}}}
// for(int i 0; i m; i){
// for(int j 0; j n;j){
// if(board[i][j] a){
// board[i][j] O;
// }
// }
// }}
};这里有几点注意的
dfs函数中除了等于X需要return等于A也需要return否则递归就没办法结束。只需要dfs淹没周围一圈的岛中间的岛不用再dfs找了直接替换就行因为本题没有让我们以整个岛为单位做一些事情。
417. 太平洋大西洋水流问题
leetcode链接题目链接 输入: heights [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2输入: heights [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]首先这题题目我都没怎么看懂理解一下题意。
输入是一个二维数组只要位于该点的值比四个方向的高就可以流向其他方向最终既可以流向右边、下边大西洋又可以流向左边、上边太平洋的符合结果输出result。
首先能想到一个很朴素的思路就是对每个点都判断一下是否能同时流向大西洋和太平洋。这种思路的实现代码如下
class Solution {
private:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};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;}bool isResult(vectorvectorint heights, int x, int y) {vectorvectorbool visited vectorvectorbool(heights.size(), vectorbool(heights[0].size(), false));// 深搜将x,y出发 能到的节点都标记上。 dfs(heights, visited, x, y);bool isPacific false;bool isAtlantic false;// 以下就是判断xy出发是否到达太平洋和大西洋 for (int j 0; j heights[0].size(); j) {if (visited[0][j]) {isPacific true;break;}}for (int i 0; i heights.size(); i) {if (visited[i][0]) {isPacific true;break;}}for (int j 0; j heights[0].size(); j) {if (visited[heights.size() - 1][j]) {isAtlantic true;break;}}for (int i 0; i heights.size(); i) {if (visited[i][heights[0].size() - 1]) {isAtlantic true;break;}}if (isAtlantic isPacific) return true;return false;}
public:vectorvectorint pacificAtlantic(vectorvectorint heights) {vectorvectorint result;// 遍历每一个点看是否能同时到达太平洋和大西洋 for (int i 0; i heights.size(); i) {for (int j 0; j heights[0].size(); j) {if (isResult(heights, i, j)) result.push_back({i, j});}}return result;}
};
这种思路很直白但很明显以上代码超时了。 来看看时间复杂度。
遍历每一个节点是 m * n遍历每一个节点的时候都要做深搜深搜的时间复杂度是 m * n
那么整体时间复杂度 就是 O(m^2 * n^2) 这是一个四次方的时间复杂度。
优化
那么我们可以 反过来想从太平洋边上的节点 逆流而上将遍历过的节点都标记上。 从大西洋的边上节点 逆流而长将遍历过的节点也标记上。 然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
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;}
};
所以 调用dfs函数只要参数传入的是 数组pacific那么地图中 每一个节点其实就遍历一次无论你调用多少次。
同理调用 dfs函数只要 参数传入的是 数组atlantic地图中每个节点也只会遍历一次。
所以以下这段代码的时间复杂度是 2 * n * m。 地图用每个节点就遍历了两次参数传入pacific的时候遍历一次参数传入atlantic的时候遍历一次。
827. 最大人工岛
leetcode链接力扣链接
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后grid 中最大的岛屿面积是多少岛屿 由一组上、下、左、右四个方向相连的 1 形成。示例 1:输入: grid [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1最终连通两个小岛得到面积为 3 的岛屿。
示例 2:输入: grid [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1岛屿的面积扩大为 4。
示例 3:输入: grid [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1面积依然为 4。https://www.programmercarl.com/0827.%E6%9C%80%E5%A4%A7%E4%BA%BA%E5%B7%A5%E5%B2%9B.html#%E4%BC%98%E5%8C%96%E6%80%9D%E8%B7%AF
先放这里放一下。题目居然是hard不太想做岛屿类的题了换换脑子。
总结
岛屿问题的dfs/bfs的代码基本大差不差主要还是主函数中处理逻辑的问题学习带有 visited的dfs的写法。
