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...
题目:
题目截图:
解题步骤:
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)
怎么样,是不是很简单,你学会了吗 ?
如果这篇文章能够帮助到您,希望您不要吝惜点赞????????和收藏????????,您的支持是我继续努力的动力 ???????? !!!
本文地址:https://blog.csdn.net/weixin_44586544/article/details/112596060