wordpress如何建站呢,网站关键词优化费用,做网站做什么好,美观网站建设物美价廉797m. 所有可能的路径
题目链接 代码随想录文章讲解链接
方法一#xff1a;DFS
用时#xff1a;11m43s
思路
时间复杂度#xff1a; O ( n ⋅ 2 n ) O(n \cdot 2^n) O(n⋅2n)#xff0c;n是节点个数#xff0c;最坏情况每个节点都可以去往任意一个在它后面的节点DFS
用时11m43s
思路
时间复杂度 O ( n ⋅ 2 n ) O(n \cdot 2^n) O(n⋅2n)n是节点个数最坏情况每个节点都可以去往任意一个在它后面的节点那么第i个节点去到最后一个节点的路径数就有 2 n − i − 2 2^{n-i-2} 2n−i−2就是当前节点和最后一个节点必走其他的节点有两种选择——走或不走。空间复杂度 O ( n ) O(n) O(n)。
C代码
class Solution {
private:vectorvectorint res;vectorint path;void backTracking(vectorvectorint graph, int i) {if (i graph.size() - 1) {res.push_back(path);return;}for (int j 0; j graph[i].size(); j) {path.push_back(graph[i][j]);backTracking(graph, graph[i][j]);path.pop_back(); // 回溯}}public:vectorvectorint allPathsSourceTarget(vectorvectorint graph) {path.push_back(0);backTracking(graph, 0);return res;}
};方法二BFS
用时16m18s
思路
队列中记录的元素是路径。
时间复杂度 O ( ) O() O()空间复杂度 O ( ) O() O()
C代码
class Solution {
public:vectorvectorint allPathsSourceTarget(vectorvectorint graph) {queuevectorint que;vectorvectorint res;que.push({0});while (!que.empty()) {vectorint path que.front();que.pop();for (int i 0; i graph[path.back()].size(); i) {vectorint tmp path;tmp.push_back(graph[path.back()][i]);if (tmp.back() graph.size() - 1) res.push_back(tmp);else que.push(tmp);}}return res;}
};看完讲解的思考
无。
代码实现遇到的问题
无。 200m. 岛屿数量
题目链接 代码随想录文章讲解链接
方法一DFS
用时17m48s
思路
遍历每个元素若是陆地则使用DFS搜索与之相邻的所有陆地并使用一个二维数组记录哪些陆地已经遍历过。 当遍历到新的岛屿时岛屿数加1。
时间复杂度 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;int dir[4][2] {0, -1, 1, 0, 0, 1, -1, 0};void dfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {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 m || nexty 0 || nexty n) !visited[nextx][nexty] grid[nextx][nexty] 1) dfs(grid, visited, nextx, nexty);}}public:int numIslands(vectorvectorchar grid) {m grid.size();n grid[0].size();vectorvectorbool visited(m, vectorbool(n, false));int res 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (!visited[i][j] grid[i][j] 1) {res;dfs(grid, visited, i, j);}}}return res;}
};方法二方法一优化
思路
可以不用数组记录哪些陆地访问过只用把访问过的陆地置0即可。
时间复杂度 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;int dir[4][2] {0, -1, 1, 0, 0, 1, -1, 0};void dfs(vectorvectorchar grid, int x, int y) {grid[x][y] 0;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (!(nextx 0 || nextx m || nexty 0 || nexty n) grid[nextx][nexty] 1) dfs(grid, nextx, nexty);}}public:int numIslands(vectorvectorchar grid) {m grid.size();n grid[0].size();int res 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {res;dfs(grid, i, j);}}}return res;}
};看完讲解的思考
代码实现遇到的问题
方法三BFS
思路
时间复杂度 O ( m ⋅ n ) O(m \cdot n) O(m⋅n)空间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n))
C代码
class Solution {
private:int m;int n;int dir[4][2] {0, -1, 1, 0, 0, 1, -1, 0};void bfs(vectorvectorchar grid, int x, int y) {queuepairint, int que;grid[x][y] 0;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] 1) {grid[nextx][nexty] 0;que.push(pairint, int(nextx, nexty));}}}}public:int numIslands(vectorvectorchar grid) {m grid.size();n grid[0].size();int res 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {res;bfs(grid, i, j);}}}return res;}
};看完讲解的思考
无。
代码实现遇到的问题
无。 695m. 岛屿的最大面积
题目链接 代码随想录文章讲解链接
方法一DFS
用时16m39s
思路
当遇到陆地时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;int area;void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 0;area 1;if (x - 1 0 grid[x - 1][y] 1) dfs(grid, x - 1, y);if (x 1 m grid[x 1][y] 1) dfs(grid, x 1, y);if (y - 1 0 grid[x][y - 1] 1) dfs(grid, x, y - 1);if (y 1 n grid[x][y 1] 1) dfs(grid, x, y 1);}public:int maxAreaOfIsland(vectorvectorint grid) {int res 0;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) {area 0;dfs(grid, i, j);res max(res, area);}}}return res;}
};方法二BFS
思路
时间复杂度 O ( m ⋅ n ) O(m \cdot n) O(m⋅n)空间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n))
C代码
class Solution {
private:int m;int n;int dir[4][2] {0, 1, 0, -1, 1, 0, -1, 0};int bfs(vectorvectorint grid, int x, int y) {int area 1;queuepairint, int que;que.push(pairint, int(x, y));grid[x][y] 0;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] 1) {grid[nextx][nexty] 0;area 1;que.push(pairint, int(nextx, nexty));}}}return area;}public:int maxAreaOfIsland(vectorvectorint grid) {int res 0;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) res max(res, bfs(grid, i, j));}}return res;}
};看完讲解的思考
无。
代码实现遇到的问题
BFS时元素入列的时候就要做标记不能在元素出列的时候才做标记不然会重复遍历。 1020m. 飞地的数量
题目链接 代码随想录文章讲解链接
方法一DFS
用时20m42s
思路
在上一题695m的基础上加多一个变量用于记录当前岛屿是否临界如果不是的话将岛屿的陆地数量记录。
时间复杂度 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;int num;bool flag;void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 0;num 1;if (x - 1 0) flag true;else if (grid[x - 1][y] 1) dfs(grid, x - 1, y);if (x 1 m) flag true;else if (grid[x 1][y] 1) dfs(grid, x 1, y);if (y - 1 0) flag true;else if (grid[x][y - 1] 1) dfs(grid, x, y - 1);if (y 1 n) flag true;else if (grid[x][y 1] 1) dfs(grid, x, y 1);}public:int numEnclaves(vectorvectorint grid) {int res 0;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) {num 0;flag false;dfs(grid, i, j);if (!flag) res num;}}}return res;}
};方法二BFS
思路
时间复杂度 O ( m ⋅ n ) O(m \cdot n) O(m⋅n)。空间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n))。
C代码
class Solution {
private:int m;int n;int dir[4][2] {0, 1, 0, -1, 1, 0, -1, 0};int bfs(vectorvectorint grid, int x, int y) {int num 1;queuepairint, int que;que.push(pairint, int(x, y));grid[x][y] 0;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) num INT_MIN;else if (grid[nextx][nexty] 1) {grid[nextx][nexty] 0;num;que.push(pairint, int(nextx, nexty));}}}return num;}public:int numEnclaves(vectorvectorint grid) {int res 0;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) res max(0, bfs(grid, i, j));}}return res;}
};看完讲解的思考
无。
代码实现遇到的问题
无。 130m. 被围绕的区域
题目链接 代码随想录文章讲解链接
方法一DFS
用时17m13s
思路
遍历位于临界的元素若是’O’则将连通的’O’变成’H’最后再将board中的所有’O’替换成’X’‘H’替换成’O’因为此时剩下的’O’是位于board内部的无法连接到外部的元素直接将其变成’X’而’H’是可以连通到外部的’O’将其变回’O’。
时间复杂度 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(vectorvectorchar board, int x, int y) {board[x][y] H;if (x - 1 0 board[x - 1][y] O) dfs(board, x - 1, y);if (x 1 m board[x 1][y] O) dfs(board, x 1, y);if (y - 1 0 board[x][y - 1] O) dfs(board, x, y - 1);if (y 1 n board[x][y 1] O) dfs(board, x, y 1);}public:void solve(vectorvectorchar board) {m board.size();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 i 0; i n; i) {if (board[0][i] O) dfs(board, 0, i);if (board[m - 1][i] O) dfs(board, m - 1, i);}for (int i 0; i m; i) {for (int j 0; j n; j) {if (board[i][j] H) board[i][j] O;else if (board[i][j] O) board[i][j] X;}}}
};方法二BFS
思路
就是遍历的方法从DFS换成BFS懒得写了。
时间复杂度 O ( m ⋅ n ) O(m \cdot n) O(m⋅n)。空间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n))。
看完讲解的思考
无。
代码实现遇到的问题
无。 最后的碎碎念
就快要一刷完代码随想录冲
