Leetcode: 【每日一题】- 2019-08-13 - 417. 太平洋大西洋水流问题

[azl397985856]

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

 

提示：

输出坐标的顺序不重要
m 和 n 都小于150
 

示例：

 

给定下面的 5x5 矩阵:

太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[watchpoints]

认领

[azl397985856]

认领

done

[xiongcaihu]

``` .js
/**

• @param {number[][]} matrix
• @return {number[][]}
• 
  
  
  
  • 逆向模式来做
  
  
• 先统计能从太平洋反流回来的坐标
• 再统计能从大西洋反流回来的坐标
• 
  
  
  
  • 最后将两个集合中都为true的坐标输出
    
    */
    
    var pacificAtlantic = function (matrix) {
    
    if (matrix.length == 0) return [];
    
    var m = matrix.length,
    
    n = matrix[0].length;
  
  

var dpt = Array.from({ // 记录能流入太平洋的位置
    length: m
}, () => new Array(n).fill(false));
var dpd = Array.from({ // 记录能流入大西洋的位置
    length: m
}, () => new Array(n).fill(false));

// 从太平洋的起点搜索，也就是最上边一排的元素位置和左边竖排元素的位置
for (var i = 0; i < matrix.length; i++) {
    for (var j = 0, len = i == 0 ? n : 1; j < len; j++) {
        temp(i, j, -1, dpt);
    }
}

// 大西洋
for (var i = 0; i < matrix.length; i++) {
    for (var j = n - 1, len = i == m - 1 ? 0 : n - 1; j >= len; j--) {
        temp(i, j, -1, dpd);
    }
}

var rel = [];
for (var i = 0; i < dpt.length; i++) {
    for (var j = 0; j < dpt[i].length; j++) {
        if (dpt[i][j] && dpt[i][j] == dpd[i][j]) {
            rel.push([i, j])
        }
    }
}

return rel;

function temp(x, y, preNumber, mem) {
    var nowNum = matrix[x] && matrix[x][y];
    if (nowNum == null) return; // 如果跨越边界，则返回
    if (mem[x][y]) { // 如果此位置已经可以流入大西洋或者太平洋，则直接返回
        return mem[x][y];
    }
    if (nowNum >= preNumber) { // 如果此位置比上一个位置的元素值大，则符合条件，然后再搜索基于它的上下左右四个位置
        mem[x][y] = true;
        temp(x - 1, y, nowNum, mem);
        temp(x + 1, y, nowNum, mem);
        temp(x, y - 1, nowNum, mem);
        temp(x, y + 1, nowNum, mem);
    }
}

};
```

执行结果：通过 显示详情
执行用时 :152 ms, 在所有 JavaScript 提交中击败了100.00%的用户
内存消耗 :41.1 MB, 在所有 JavaScript 提交中击败了100.00%的用户

[azl397985856]

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 * 
 * 逆向模式来做
 * 先统计能从太平洋反流回来的坐标
 * 再统计能从大西洋反流回来的坐标
 * 
 * 最后将两个集合中都为true的坐标输出
 */
var pacificAtlantic = function (matrix) {
    if (matrix.length == 0) return [];
    var m = matrix.length,
        n = matrix[0].length;

    var dpt = Array.from({ // 记录能流入太平洋的位置
        length: m
    }, () => new Array(n).fill(false));
    var dpd = Array.from({ // 记录能流入大西洋的位置
        length: m
    }, () => new Array(n).fill(false));

    // 从太平洋的起点搜索，也就是最上边一排的元素位置和左边竖排元素的位置
    for (var i = 0; i < matrix.length; i++) {
        for (var j = 0, len = i == 0 ? n : 1; j < len; j++) {
            temp(i, j, -1, dpt);
        }
    }

    // 大西洋
    for (var i = 0; i < matrix.length; i++) {
        for (var j = n - 1, len = i == m - 1 ? 0 : n - 1; j >= len; j--) {
            temp(i, j, -1, dpd);
        }
    }

    var rel = [];
    for (var i = 0; i < dpt.length; i++) {
        for (var j = 0; j < dpt[i].length; j++) {
            if (dpt[i][j] && dpt[i][j] == dpd[i][j]) {
                rel.push([i, j])
            }
        }
    }

    return rel;

    function temp(x, y, preNumber, mem) {
        var nowNum = matrix[x] && matrix[x][y];
        if (nowNum == null) return; // 如果跨越边界，则返回
        if (mem[x][y]) { // 如果此位置已经可以流入大西洋或者太平洋，则直接返回
            return mem[x][y];
        }
        if (nowNum >= preNumber) { // 如果此位置比上一个位置的元素值大，则符合条件，然后再搜索基于它的上下左右四个位置
            mem[x][y] = true;
            temp(x - 1, y, nowNum, mem);
            temp(x + 1, y, nowNum, mem);
            temp(x, y - 1, nowNum, mem);
            temp(x, y + 1, nowNum, mem);
        }
    }
};

执行结果：通过 显示详情
执行用时 :152 ms, 在所有 JavaScript 提交中击败了100.00%的用户
内存消耗 :41.1 MB, 在所有 JavaScript 提交中击败了100.00%的用户

是一个常规思路。非常好.

BTW, 为什么我的144ms，才击败51.25%

✔ Accepted
✔ 113/113 cases passed (144 ms)
✔ Your runtime beats 51.25 % of javascript submissions
✔ Your memory usage beats 100 % of javascript submissions (43.9 MB)

[azl397985856]

我贴一下我的代码。

思路：

总体思路还是回溯，我们对能够流入太平洋的（第一行和第一列）开始进行上下左右探测。

同样我们对能够流入大西洋的（最后一行和最后一列）开始进行上下左右探测。

最后将探测结果进行合并即可。合并的条件就是当前单元既能流入太平洋又能流入大西洋。

代码：

function dfs(i, j, height, m, matrix, rows, cols) {
  if (i >= rows || i < 0) return;
  if (j >= cols || j < 0) return;

  if (matrix[i][j] < height) return;

  if (m[i][j] === true) return;

  m[i][j] = true;

  dfs(i + 1, j, matrix[i][j], m, matrix, rows, cols);
  dfs(i - 1, j, matrix[i][j], m, matrix, rows, cols);
  dfs(i, j + 1, matrix[i][j], m, matrix, rows, cols);
  dfs(i, j - 1, matrix[i][j], m, matrix, rows, cols);
}
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function(matrix) {
  const rows = matrix.length;
  if (rows === 0) return [];
  const cols = matrix[0].length;
  const pacific = Array.from({ length: rows }, () => Array(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => Array(cols).fill(false));
  const res = [];

  for (let i = 0; i < rows; i++) {
    dfs(i, 0, 0, pacific, matrix, rows, cols);
    dfs(i, cols - 1, 0, atlantic, matrix, rows, cols);
  }

  for (let i = 0; i < cols; i++) {
    dfs(0, i, 0, pacific, matrix, rows, cols);
    dfs(rows - 1, i, 0, atlantic, matrix, rows, cols);
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (pacific[i][j] === true && atlantic[i][j] === true) res.push([i, j]);
    }
  }

  return res;
};

扩展：

如果题目改为能够流入大西洋或者太平洋，我们只需要最后合并的时候，条件改为求或即可。