新沂建设工程交易中心,seo网站规划,WordPress分类置顶插件,nodejs的网站开发目录 Leetcode695. 岛屿的最大面积Leetcode1020. 飞地的数量Leetcode130. 被围绕的区域Leetcode417. 太平洋大西洋水流问题Leetcode827.最大人工岛 Leetcode695. 岛屿的最大面积 文章链接#xff1a;代码随想录 题目链接#xff1a;695. 岛屿的最大面积 思路#xff1a;dfs … 目录 Leetcode695. 岛屿的最大面积Leetcode1020. 飞地的数量Leetcode130. 被围绕的区域Leetcode417. 太平洋大西洋水流问题Leetcode827.最大人工岛 Leetcode695. 岛屿的最大面积 文章链接代码随想录 题目链接695. 岛屿的最大面积 思路dfs
class Solution {
public:int count;int dir[4][2] {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){for (int i 0; i 4; i){int nex x dir[i][0];int ney y dir[i][1];if (nex 0 || nex grid.size() || ney 0 || ney grid[0].size()) continue;if (!visited[nex][ney] grid[nex][ney] 1){visited[nex][ney] true;count;dfs(grid, visited, nex, ney);}}}int maxAreaOfIsland(vectorvectorint grid) {int result 0;vectorvectorbool visited(grid.size(), vectorbool(grid[0].size(), 0));for (int i 0; i grid.size(); i){for (int j 0; j grid[0].size(); j){if (!visited[i][j] grid[i][j] 1){visited[i][j] true;count 1;dfs (grid, visited, i, j);result max(result, count);}}}return result;}};bfs
class Solution {
public:int count;int dir[4][2] {1, 0, -1, 0, 0, 1, 0, -1};void bfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){queuepairint, int que;que.push({x, y});while(!que.empty()){pairint, int cur que.front();que.pop();for (int i 0; i 4; i){int nex cur.first dir[i][0];int ney cur.second dir[i][1];if (nex 0 || nex grid.size() || ney 0 || ney grid[0].size()) continue;if (!visited[nex][ney] grid[nex][ney] 1){visited[nex][ney] true;count;que.push({nex, ney});}}}}int maxAreaOfIsland(vectorvectorint grid) {int result 0;vectorvectorbool visited(grid.size(), vectorbool(grid[0].size(), 0));for (int i 0; i grid.size(); i){for (int j 0; j grid[0].size(); j){if (!visited[i][j] grid[i][j] 1){visited[i][j] true;count 1;bfs (grid, visited, i, j);result max(result, count);}}}return result;}};Leetcode1020. 飞地的数量 文章链接代码随想录 题目链接1020. 飞地的数量 思路dfs
class Solution {
public:int count 0;int dir[4][2] {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vectorvectorint grid, int x, int y){grid[x][y] 0;count;for (int i 0; i 4; i){int nex x dir[i][0];int ney y dir[i][1];if (nex 0 || nex grid.size() || ney 0 || ney grid[0].size()) continue;if (grid[nex][ney] 1) dfs(grid, nex, ney);}return ;}int numEnclaves(vectorvectorint grid) {int m grid.size();int n grid[0].size();int result 0;for (int i 0; i m; i){if(grid[i][0] 1) dfs(grid, i, 0);if(grid[i][n - 1] 1) dfs(grid, i, n - 1);}for (int j 0; j n; j){if (grid[0][j] 1) dfs(grid, 0, j);if (grid[m - 1][j] 1) dfs(grid, m - 1, j);}for (int i 0; i m; i){for (int j 0; j n; j){if (grid[i][j] 1) {count 0;dfs(grid, i, j);result count;}}}return result;}
};Leetcode130. 被围绕的区域 文章链接代码随想录 题目链接130. 被围绕的区域 思路dfs
class Solution {
public:int dir[4][2] {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vectorvectorchar board, int x, int y){board[x][y] A;for (int i 0; i 4; i){int nex x dir[i][0];int ney y dir[i][1];if (nex 0 || nex board.size() || ney 0 || ney board[0].size()) continue;if (board[nex][ney] O) dfs(board, nex, ney);}} void solve(vectorvectorchar board) {int m board.size();int n board[0].size();for (int i 0; i m; i){if (board[i][0] O) dfs(board, i, 0);if (board[i][n - 1] O) dfs(board, i, n - 1);}for (int j 0; j n; j){if (board[0][j] O) dfs(board, 0, j);if (board[m - 1][j] O) dfs(board, m - 1, j);}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;}}}
};Leetcode417. 太平洋大西洋水流问题 文章链接代码随想录 题目链接417. 太平洋大西洋水流问题 思路注意终止条件 if (visited[x][y]) return ;
class Solution {
public:int dir[4][2] {1, 0, -1, 0, 0, 1, 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 nex x dir[i][0];int ney y dir[i][1];if (nex 0 || nex heights.size() || ney 0 || ney heights[0].size()) continue;if (heights[x][y] heights[nex][ney]) dfs(heights, visited, nex, ney);}}vectorvectorint pacificAtlantic(vectorvectorint heights) {int m heights.size();int n heights[0].size();vectorvectorbool pacific(m, vectorbool(n, false));vectorvectorbool atlantic(m, vectorbool(n, false));vectorvectorint result;for (int i 0; i m; i){dfs(heights, pacific, i, 0);dfs(heights, atlantic, i, n - 1);}for (int j 0; j n; j){dfs(heights, pacific, 0, j);dfs(heights, atlantic, m - 1, j);}for (int i 0; i m; i){for (int j 0; j n; j){if (pacific[i][j] atlantic[i][j]) result.push_back({i, j});}}return result;}
};Leetcode827.最大人工岛 文章链接代码随想录 题目链接827.最大人工岛 思路dfs先用map记录原有的每块陆地的大小再在0处遍历连接陆地选择最大值。
class Solution {
public:int count;int mark 2;int dir[4][2] {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){if (visited[x][y] || grid[x][y] 0) return ;visited[x][y] true;count;grid[x][y] mark;for (int i 0; i 4; i){int nex x dir[i][0];int ney y dir[i][1];if (nex 0 || nex grid.size() || ney 0 || ney grid[0].size()) continue;dfs(grid, visited, nex, ney);}}int largestIsland(vectorvectorint grid) {int m grid.size();int n grid[0].size();vectorvectorbool visited(m, vectorbool(n, false));unordered_mapint, int gridNum;bool isAllGrid true;int result 0;for (int i 0; i m; i){for (int j 0; j n; j){if (grid[i][j] 0) isAllGrid false;if (!visited[i][j] grid[i][j] 1){count 0;dfs(grid, visited, i, j);gridNum[mark] count;mark;}}}// cout count endl;// cout gridNum[2] endl;if (isAllGrid) return n * m;unordered_setint visitedGrid;for (int i 0; i m; i){for (int j 0; j n; j){visitedGrid.clear();if (grid[i][j] 0){count 1;for (int k 0; k 4; k){int nex i dir[k][0];int ney j dir[k][1];if (nex 0 || nex grid.size() || ney 0 || ney grid[0].size()) continue;if (visitedGrid.count(grid[nex][ney]) 0){count gridNum[grid[nex][ney]];visitedGrid.insert(grid[nex][ney]);}}result max(result, count);}}}return result;}
};图论第二天打卡整体来说套路感挺重的理解和做起来挺简单的但写多了也头晕哈哈加油
