LeetCode417.太平洋大西洋水流问题
来源:8-7 floodfill算法,一类经典问题 Number of Islands-
慕盖茨3358155
2022-04-28
老师,可以帮忙看看代码问题吗?我感觉思路没有问题,但是过不了。
我的思路:遍历每一个点,对每一个点都进行dfs,如果a 和 b都是true,说明两个海洋都可以流入。。。。
class Solution {
public:
int idx[4] = {-1, 0, 1, 0};
int idy[4] = {0, 1, 0, -1};
vector<vector<bool>> book; //记录某个结点是否遍历过
int n; //点数
bool a = false, b = false; // 是否可流入pacific, 是否流入atlantic
void dfs(vector<vector<int>>& heights, int x, int y) {
book[x][y] = true;
for(int i = 0; i < 4; i++) {
int newx = idx[i] + x, newy = idy[i] + y;
if(newx < 0 || newy < 0){ a = true; continue; }//进入了pacific
if(newx >= n || newy >= n){ b = true; continue; }//进入入了atlantic
if(heights[x][y] > heights[newx][newy] && !book[newx][newy])
dfs(heights, newx, newy);
}
book[x][y] = false;
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//数组的初始化
n = heights.size();
book = vector<vector<bool>>(n, vector<bool>(n, false));
vector<vector<int>> res;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
dfs(heights, i, j);
if(a && b) res.push_back( {i, j} );
a = b = false;
}
return res;
}
};
1回答
-
你现在的代码的核心逻辑问题是:题目中的要求,如果相邻格子的高度是相同的,水依然可以流过去。但是你的逻辑只有 heights[x][y] > heights[newx][newy] 才可以流过去。
应该是:heights[x][y] >= heights[newx][newy]
但是你的代码,如果修改成 heights[x][y] >= heights[newx][newy],依然会有问题。
出问题的测试用例是如果所有格子都相同。可以测试一下,然后再思考一下如何解决?
==========
另:你的这个思路即使走通了,也很有可能 tle。假设整个 grid 是 n*n 的。对每一个点做一遍 dfs,每一次 dfs 都是 n*n 的,整体就是 n^4 的。对于 n = 200,n^4 就是1.6 * 10^9,这个规模是很高的。
这个问题更好的解决方案是,反向的,从太平洋或者大西洋的水“逆流”去看能逆着走到哪里。如果一个格子既能从大西洋逆流流到,又能从太平洋逆流留到,则这个格子可以放入 res 中。
参考代码(Java 的,但应该很好理解):https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0417-Pacific-Atlantic-Water-Flow/java-0417/src/Solution.java
继续加油!:)
112022-05-01
相似问题