欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JavaScript实现 - LeetCode刷题 -【太平洋大西洋水流问题】- 第 417 题 !!!

程序员文章站 2022-06-26 17:26:39
题目:LeetCode题目链接题目截图:解题步骤:1.新建两个矩阵,分别记录能流到两个大洋的坐标2.从海岸线,多管齐下,同时深度优先遍历图,过程中填充上述矩阵3.遍历上面两个矩阵,找出同时能流到两个大洋的坐标代码:/** * @param {number[][]} matrix * @return {number[][]} */var pacificAtlantic = function (matrix) { if (!matrix || !matrix[0]) return...

题目:

LeetCode题目链接

题目截图:

JavaScript实现 - LeetCode刷题 -【太平洋大西洋水流问题】- 第 417 题 !!!

解题步骤:

1.新建两个矩阵,分别记录能流到两个大洋的坐标
2.从海岸线,多管齐下,同时深度优先遍历图,过程中填充上述矩阵
3.遍历上面两个矩阵,找出同时能流到两个大洋的坐标

代码:

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix) {
  if (!matrix || !matrix[0]) return []; 
  const m = matrix.length; 
  const n = matrix[0].length; 
  const flow1 = Array.from({ length: m }, () => new Array(n).fill(false));
  const flow2 = Array.from({ length: m }, () => new Array(n).fill(false));  
  const dfs = (r, c, flow) => {
    flow[r][c] = true;  
    [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]].forEach(
      ([nr, nc]) => {
        if (
          nr >= 0 && nr < m &&
          nc >= 0 && nc < n &&
          !flow[nr][nc] &&
          matrix[nr][nc] >= matrix[r][c]
        ) {
          dfs(nr, nc, flow);
        }
      }
    );
  };
  for (let r = 0; r < m; r++) {
    dfs(r, 0, flow1); 
    dfs(r, n - 1, flow2); 
  }
  for (let c = 0; c < n; c++) { 
    dfs(0, c, flow1);
    dfs(m - 1, c, flow2);
  }
  const res = [];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (flow1[r][c] && flow2[r][c]) res.push([r, c]);
    }
  }
  return res;
};

时间复杂度分析:

时间复杂度是O(m * n),因为每个点都过了一遍,m和n分别是矩阵的行数和列数

空间复杂度分析:

空间复杂度是O(m * n)

怎么样,是不是很简单,你学会了吗 ?

JavaScript实现 - LeetCode刷题 -【太平洋大西洋水流问题】- 第 417 题 !!!

JavaScript实现 - LeetCode刷题 -【太平洋大西洋水流问题】- 第 417 题 !!!

如果这篇文章能够帮助到您,希望您不要吝惜点赞????????和收藏????????,您的支持是我继续努力的动力 ???????? !!!

本文地址:https://blog.csdn.net/weixin_44586544/article/details/112596060