外汇网站建设公司,wordpress获取指定图片大小,互联网平台推广方案,模板网点地址信息错误130. 被围绕的区域 文档讲解 #xff1a;代码随想录 - 130. 被围绕的区域 状态#xff1a;开始学习。 思路#xff1a;
步骤一#xff1a; 深搜或者广搜将地图周边的 ‘O’ 全部改成 ’A’#xff0c;如图所示#xff1a; 步骤二#xff1a; 再遍历地图#xff0c;将 …130. 被围绕的区域 文档讲解 代码随想录 - 130. 被围绕的区域 状态开始学习。 思路
步骤一 深搜或者广搜将地图周边的 ‘O’ 全部改成 ’A’如图所示 步骤二 再遍历地图将 ‘O’ 全部改成 ‘X’地图中间的 ‘O’ 改成了 ‘X’ 将 ‘A’ 改回 ‘O’保留的地图周边的‘O’如图所示
本题代码dfs
class Solution {
private:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向void dfs(vectorvectorchar board, int x, int y) {board[x][y] A;for (int i 0; i 4; i) { // 向四个方向遍历int nextx x dir[i][0];int nexty y dir[i][1];// 超过边界if (nextx 0 || nextx board.size() || nexty 0 || nexty board[0].size()) continue;// 不符合条件不继续遍历if (board[nextx][nexty] X || board[nextx][nexty] A) continue;dfs (board, nextx, nexty);}return;}public:void solve(vectorvectorchar board) {int n board.size(), m board[0].size(); // 步骤一// 从左侧边和右侧边 向中间遍历for (int i 0; i n; i) {if (board[i][0] O) dfs(board, i, 0);if (board[i][m - 1] O) dfs(board, i, m - 1);}// 从上边和下边 向中间遍历for (int j 0; j m; j) {if (board[0][j] O) dfs(board, 0, j);if (board[n - 1][j] O) dfs(board, n - 1, j);}// 步骤二for (int i 0; i n; i) {for (int j 0; j m; j) {if (board[i][j] O) board[i][j] X;if (board[i][j] A) board[i][j] O;}}}
};417. 太平洋大西洋水流问题 文档讲解 代码随想录 - 417. 太平洋大西洋水流问题 状态开始学习。 思路
从太平洋的边上的节点 逆流而上将遍历过的节点都标记上。从大西洋的边上节点 逆流而长将遍历过的节点也标记上。然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
本题代码dfs
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;}
};827. 最大人工岛 文档讲解 代码随想录 - 827. 最大人工岛 状态开始学习。 思路 步骤一 一次遍历地图得出各个岛屿的面积并做编号记录。可以使用map记录key为岛屿编号value为岛屿面积 步骤二 再遍历地图遍历0的方格因为要将0变成1并统计该1由0变成的1周边岛屿面积将其相邻面积相加在一起遍历所有 0 之后就可以得出 选一个0变成1 之后的最大面积。 本题代码dfs
class Solution {
private:int count;int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] 0) return; // 终止条件访问过的节点 或者 遇到海水visited[x][y] true; // 标记访问过grid[x][y] mark; // 给陆地标记新标签count;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 越界了直接跳过dfs(grid, visited, nextx, nexty, mark);}}public:int largestIsland(vectorvectorint grid) {int n grid.size(), m grid[0].size();vectorvectorbool visited vectorvectorbool(n, vectorbool(m, false)); // 标记访问过的点unordered_mapint ,int gridNum;int mark 2; // 记录每个岛屿的编号bool isAllGrid true; // 标记是否整个地图都是陆地for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0) isAllGrid false;if (!visited[i][j] grid[i][j] 1) {count 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] count; // 记录每一个岛屿的面积mark; // 记录下一个岛屿编号}}}if (isAllGrid) return n * m; // 如果都是陆地返回全面积// 以下逻辑是根据添加陆地的位置计算周边岛屿面积之和int result 0; // 记录最后结果unordered_setint visitedGrid; // 标记访问过的岛屿for (int i 0; i n; i) {for (int j 0; j m; j) {int count 1; // 记录连接之后的岛屿数量visitedGrid.clear(); // 每次使用时清空if (grid[i][j] 0) {for (int k 0; k 4; k) {int neari i dir[k][1]; // 计算相邻坐标int nearj j dir[k][0];if (neari 0 || neari grid.size() || nearj 0 || nearj grid[0].size()) continue;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result max(result, count);}}return result;}
};
