青岛市北建设集团网站,建程网官网平台,四川网站建设电话,软件开发流程八个步骤417m. 太平洋大西洋水流问题
题目链接 代码随想录文章讲解链接
方法一#xff1a;
用时#xff1a;1h0m58s
思路
直接找哪些点既可以到达太平洋又可以到达大西洋比较麻烦#xff0c;换个角度#xff0c;找到太平洋可以逆流而上到达的点#xff0c;再找到大西洋可以逆…417m. 太平洋大西洋水流问题
题目链接 代码随想录文章讲解链接
方法一
用时1h0m58s
思路
直接找哪些点既可以到达太平洋又可以到达大西洋比较麻烦换个角度找到太平洋可以逆流而上到达的点再找到大西洋可以逆流而上到达的点两者的交集就是所需要的答案。 用两个二维数组分别记录太平洋和大西洋可以逆流而上达到的点对边界的点使用DFS。
时间复杂度 O ( m ⋅ n ) O(m \cdot n) O(m⋅n)。空间复杂度 O ( m ⋅ n ) O(m \cdot n) O(m⋅n)。
C代码
class Solution {
private:int m;int n;void dfs(vectorvectorint heights, vectorvectorbool visited, int x, int y) {visited[x][y] true;if (x - 1 0 !visited[x - 1][y] heights[x - 1][y] heights[x][y]) dfs(heights, visited, x - 1, y);if (x 1 m !visited[x 1][y] heights[x 1][y] heights[x][y]) dfs(heights, visited, x 1, y);if (y - 1 0 !visited[x][y - 1] heights[x][y - 1] heights[x][y]) dfs(heights, visited, x, y - 1);if (y 1 n !visited[x][y 1] heights[x][y 1] heights[x][y]) dfs(heights, visited, x, y 1);}public:vectorvectorint pacificAtlantic(vectorvectorint heights) {m heights.size();n heights[0].size();vectorvectorbool pacific(m, vectorbool(n, false));vectorvectorbool atlantic(m, vectorbool(n, false));vectorvectorint res;for (int i 0; i m; i) {if (!pacific[i][0]) dfs(heights, pacific, i, 0);if (!atlantic[i][n - 1]) dfs(heights, atlantic, i, n - 1);}for (int i 0; i n; i) {if (!pacific[0][i]) dfs(heights, pacific, 0, i);if (!atlantic[m - 1][i]) dfs(heights, atlantic, m - 1, i);}for (int i 0; i m; i) {for (int j 0; j n; j) {if (pacific[i][j] atlantic[i][j]) res.push_back({i, j});}}return res;}
};方法二BFS
用时6m53s
思路
时间复杂度 O ( m n ) O(mn) O(mn)。空间复杂度 O ( m n ) O(mn) O(mn)。
C代码
class Solution {
private:int m;int n;int dir[4][2] {0, 1, 0, -1, 1, 0, -1, 0};void bfs(vectorvectorint heights, vectorvectorbool visited, int x, int y) {queuepairint, int que;que.push(pairint, int(x, y));visited[x][y] true;while (!que.empty()) {pairint, int tmp que.front();que.pop();for (int i 0; i 4; i) {int nextx tmp.first dir[i][0];int nexty tmp.second dir[i][1];if (!(nextx 0 || nextx m || nexty 0 || nexty n) !visited[nextx][nexty] heights[nextx][nexty] heights[tmp.first][tmp.second]) {visited[nextx][nexty] true;que.push(pairint, int(nextx, nexty));}}}}public:vectorvectorint pacificAtlantic(vectorvectorint heights) {m heights.size();n heights[0].size();vectorvectorbool pacific(m, vectorbool(n, false));vectorvectorbool atlantic(m, vectorbool(n, false));vectorvectorint res;for (int i 0; i m; i) {if (!pacific[i][0]) bfs(heights, pacific, i, 0);if (!atlantic[i][n - 1]) bfs(heights, atlantic, i, n - 1);}for (int i 0; i n; i) {if (!pacific[0][i]) bfs(heights, pacific, 0, i);if (!atlantic[m - 1][i]) bfs(heights, atlantic, m - 1, i);}for (int i 0; i m; i) {for (int j 0; j n; j) {if (pacific[i][j] atlantic[i][j]) res.push_back({i, j});}}return res;}
};看完讲解的思考
逆流而上真妙啊。
代码实现遇到的问题
无。 841m. 钥匙和房间
题目链接 代码随想录文章讲解链接
方法一DFS
用时12m21s
思路
DFS一遍若有房间没走过则返回false。
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
C代码
class Solution {
private:void dfs(vectorvectorint rooms, vectorbool visited, int i) {visited[i] true;for (int j 0; j rooms[i].size(); j) {if (!visited[rooms[i][j]]) dfs(rooms, visited, rooms[i][j]);}}public:bool canVisitAllRooms(vectorvectorint rooms) {vectorbool visited(rooms.size(), false);dfs(rooms, visited, 0);for (int i 0; i rooms.size(); i) {if (!visited[i]) return false;}return true;}
};方法二BFS
用时4m46s
思路
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
C代码
class Solution {
public:bool canVisitAllRooms(vectorvectorint rooms) {vectorbool visited(rooms.size(), false);queueint que;visited[0] true;que.push(0);while (!que.empty()) {int curRoom que.front();que.pop();for (int i 0; i rooms[curRoom].size(); i) {if (!visited[rooms[curRoom][i]]) {visited[rooms[curRoom][i]] true;que.push(rooms[curRoom][i]);}}}for (int i 1; i rooms.size(); i) {if (!visited[i]) return false;}return true;}
};看完讲解的思考
无。
代码实现遇到的问题
无。 463e. 岛屿的周长
题目链接 代码随想录文章讲解链接
方法一DFS
用时7m37s
思路
在DFS的过程中某个方向到达边界或者到达水域则说明该方向是一条边周长1。
时间复杂度 O ( m n ) O(mn) O(mn)。空间复杂度 O ( m n ) O(mn) O(mn)。
C代码
class Solution {
private:int m;int n;int perimeter;void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 2;if (x - 1 0 || grid[x - 1][y] 0) perimeter;else if (grid[x - 1][y] ! 2) dfs(grid, x - 1, y);if (x 1 m || grid[x 1][y] 0) perimeter;else if (grid[x 1][y] ! 2) dfs(grid, x 1, y);if (y - 1 0 || grid[x][y - 1] 0) perimeter;else if (grid[x][y - 1] ! 2) dfs(grid, x, y - 1);if (y 1 n || grid[x][y 1] 0) perimeter;else if (grid[x][y 1] ! 2) dfs(grid, x, y 1);}public:int islandPerimeter(vectorvectorint grid) {m grid.size();n grid[0].size();for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {dfs(grid, i, j);return perimeter;}}}return perimeter;}
};方法二BFS
用时4m55s
思路
时间复杂度 O ( m n ) O(mn) O(mn)。空间复杂度 O ( m n ) O(mn) O(mn)。
C代码
class Solution {
private:int m;int n;int perimeter;int dir[4][2] {0, 1, 0, -1, 1, 0, -1, 0};void bfs(vectorvectorint grid, int x, int y) {queuepairint, int que;grid[x][y] 2;que.push(pairint, int(x, y));while (!que.empty()) {pairint, int tmp que.front();que.pop();for (int i 0; i 4; i) {int nextx tmp.first dir[i][0];int nexty tmp.second dir[i][1];if (nextx 0 || nextx m || nexty 0 || nexty n || grid[nextx][nexty] 0) perimeter;else if (grid[nextx][nexty] ! 2) {grid[nextx][nexty] 2;que.push(pairint, int(nextx, nexty));}}}}public:int islandPerimeter(vectorvectorint grid) {m grid.size();n grid[0].size();for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {bfs(grid, i, j);return perimeter;}}}return perimeter;}
};方法三遍历
用时7m11s
思路
其实直接遍历就行了遇到陆地就判断一下四条边根本不用dfs、bfs这么复杂…
时间复杂度 O ( m n ) O(mn) O(mn)。空间复杂度 O ( 1 ) O(1) O(1)。
C代码
class Solution {
public:int islandPerimeter(vectorvectorint grid) {int m grid.size();int n grid[0].size();int perimeter 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {if (i - 1 0 || grid[i - 1][j] 0) perimeter;if (i 1 m || grid[i 1][j] 0) perimeter;if (j - 1 0 || grid[i][j - 1] 0) perimeter;if (j 1 n || grid[i][j 1] 0) perimeter;}}}return perimeter;}
};看完讲解的思考
无。
代码实现遇到的问题
无。 最后的碎碎念
一刷倒数第二天
