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回答

liuyubobobo

2022-04-29

你现在的代码的核心逻辑问题是:题目中的要求,如果相邻格子的高度是相同的,水依然可以流过去。但是你的逻辑只有 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


继续加油!:)

1
1
慕盖茨3358155
谢谢老师,已经解决了~
2022-05-01
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程