Algorithm
lc417_太平洋大西洋水流问题
思路：
暴力就是每个节点都尝试dfs能否流动到左上边界之一和右下边界之一。
优化一点就是从边界开始搜索，然后进行记忆。
dfs，bfs皆可。可以看题解复习一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
vector<vector<int>> heights;
void dfs(int row, int col, vector<vector<bool>> & ocean) {
int m = ocean.size();
int n = ocean[0].size();
if (ocean[row][col]) {
return;
}
ocean[row][col] = true;
for (int i = 0; i < 4; i++) {
int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
dfs(newRow, newCol, ocean);
}
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
this->heights = heights;
int m = heights.size();
int n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
dfs(i, 0, pacific);
}
for (int j = 1; j < n; j++) {
dfs(0, j, pacific);
}
for (int i = 0; i < m; i++) {
dfs(i, n - 1, atlantic);
}
for (int j = 0; j < n - 1; j++) {
dfs(m - 1, j, atlantic);
}
vector<vector<int>> result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
vector<int> cell;
cell.emplace_back(i);
cell.emplace_back(j);
result.emplace_back(cell);
}
}
}
return result;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
vector<vector<int>> heights;
void bfs(int row, int col, vector<vector<bool>> & ocean) {
if (ocean[row][col]) {
return;
}
int m = heights.size();
int n = heights[0].size();
ocean[row][col] = true;
queue<pair<int, int>> qu;
qu.emplace(row, col);
while (!qu.empty()) {
auto [row, col] = qu.front();
qu.pop();
for (int i = 0; i < 4; i++) {
int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col] && !ocean[newRow][newCol]) {
ocean[newRow][newCol] = true;
qu.emplace(newRow, newCol);
}
}
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
this->heights = heights;
int m = heights.size();
int n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
bfs(i, 0, pacific);
}
for (int j = 1; j < n; j++) {
bfs(0, j, pacific);
}
for (int i = 0; i < m; i++) {
bfs(i, n - 1, atlantic);
}
for (int j = 0; j < n - 1; j++) {
bfs(m - 1, j, atlantic);
}
vector<vector<int>> result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
vector<int> cell;
cell.emplace_back(i);
cell.emplace_back(j);
result.emplace_back(cell);
}
}
}
return result;
}
};
|
Review
The Rebirth of Everything
写得很热血澎湃，说Dex会崛起:
- 不再是Cex机构分蛋糕，而是Dex和用户一起分蛋糕。
- 不再让钱掌控在Cex手里，而是用户掌控在自己的钱包里。
- 解决Dex交易速度问题，让Dex拥有和Cex一样的交易速度。
Tips
DieWithZero读后感补充
大胆尝试任何自己想做的事，人生是体验，只要最坏结果能接受，想做就去做，趁着还有时间，赶紧去冒险。
就像做多，风险有限收益无限，而不是困在一个牛马工位上裸空生命，收益有限风险无限。(当然先在工位套保赚点启动安全资金是挺好的)
Share
《养了猫，我就后悔了》
养猫常识书，建议养猫人都读一下。