- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址: https://leetcode.com/problems/pacific-atlantic-water-flow/description/
Given an m x n
matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean"
touches the left and top edges of the matrix and the ``"Atlantic ocean"```touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right)
from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
1、 Theorderofreturnedgridcoordinatesdoesnotmatter.;
2、 Bothmandnarelessthan150.;
Example:
Given the following 5x5 matrix:
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
上面一条边和左边一条边代表的是太平洋,右边一条边和下边一条边代表的是大西洋。
现在告诉你水往低处流,问哪些位置的水能同时流进太平洋和大西洋?
要解决的问题:哪些位置的雨水能同时流进太平洋和大西洋。 重要思路:将水的流向反转,假设太平洋和大西洋的水 从低向高 “攀登”,分别能到达哪些位置,分别用 p_visited
和 a_visited
表示。两者的交集就代表能同时流向太平洋和大西洋的位置。
直接DFS求解。一般来说 DFS 需要有固定的起点,但是对于本题,4 条边都是能与大洋接壤的,那么就把 4条边界的每个位置都算作 DFS 的起点 。
使用两个二维数组 p_visited
和 a_visited
,分别记录太平洋和大西洋的水能从低向高“攀登”到的位置。
然后对4 条边进行遍历,看以这些边的每个位置为起点,进行攀登;把能到达的哪些的位置,分别在 p_visited
和 a_visited
标记出来。
注意了,因为是从边界向中间去“攀登”,所以,这个时候是新的点要比当前的点海拔高才行。
Python代码如下:
class Solution(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix or not matrix[0]: return []
m, n = len(matrix), len(matrix[0])
p_visited = [[False] * n for _ in range(m)]
a_visited = [[False] * n for _ in range(m)]
for i in range(m):
self.dfs(p_visited, matrix, m, n, i, 0)
self.dfs(a_visited, matrix, m, n, i, n -1)
for j in range(n):
self.dfs(p_visited, matrix, m, n, 0, j)
self.dfs(a_visited, matrix, m, n, m - 1, j)
res = []
for i in range(m):
for j in range(n):
if p_visited[i][j] and a_visited[i][j]:
res.append([i, j])
return res
def dfs(self, visited, matrix, m, n, i, j):
visited[i][j] = True
directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for dire in directions:
x, y = i + dire[0], j + dire[1]
if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] < matrix[i][j]:
continue
self.dfs(visited, matrix, m, n, x, y)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
C++代码如下:
class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
const int M = matrix.size();
const int N = matrix[0].size();
vector<vector<bool>> p_visited(M, vector<bool>(N));
vector<vector<bool>> a_visited(M, vector<bool>(N));
for (int i = 0; i < M; ++i) {
dfs(matrix, p_visited, i, 0);
dfs(matrix, a_visited, i, N - 1);
}
for (int j = 0; j < N; ++j) {
dfs(matrix, p_visited, 0, j);
dfs(matrix, a_visited, M - 1, j);
}
vector<pair<int, int>> res;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (p_visited[i][j] && a_visited[i][j]) {
res.push_back({i, j});
}
}
}
return res;
}
void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j) {
const int M = matrix.size();
const int N = matrix[0].size();
visited[i][j] = true;
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (auto d : dirs) {
int nx = i + d.first;
int ny = j + d.second;
if (nx >= 0 && nx < M && ny >= 0 && ny < N && !visited[nx][ny] && matrix[nx][ny] >= matrix[i][j]) {
dfs(matrix, visited, nx, ny);
}
}
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
最坏情况下的时间复杂度:O((M+N)∗MN) 空间复杂度: O(MN)。
参考资料:
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在尝试实现 kotlin stateflow,但不知道它不起作用的原因。 当前输出: 验证34567 预期输出: 验证 34567 验证失败 package stateflowDuplicate
最近我发现了一个我无法理解的流行为。 问题描述 考虑这种情况:你有一个父 flow 并且在它的 collect 中,你将有一个“子”flow 并调用 .collect(),像这样: parentFlo
我想通过 UML2 事件图为以下事件建模: 执行操作 1。此操作产生两个输出参数: Object1和对象 2。 执行操作 2。此操作需要 Object2 作为输入参数。它不需要 Object1 作为输
在 Vaadin 8 中,您可以在 Tab(属于 TabSheet)上设置一个图标: tab#setIcon(...) 在 Vaadin Flow(目前使用 14.1)中,我不知道如何在 Tab(属于
有什么办法可以做到这一点吗?如果存储库仅在 .git/config 中包含 git-flow 指令(如 ),则该存储库是否被视为已初始化 .... [gitflow "branch"] mas
the 2nd collecting below does not collect until I remove the first one. also read from [Manuel Vi
在官方示例中,他们总是有 /* @flow */在页面顶部。现在这对现有项目来说很好,很有帮助,我想选择加入每个文件的流程。从头开始构建一个新项目我只想在任何地方进行流类型检查,而不必输入 /* @f
Vaadin 突然停止构建我的库并出现以下错误。我已经跳了 Vaadin 舞(还有很多其他的东西),但我现在没主意了。我尝试为生产构建库(但对于开发也失败了)。 我正在使用 Vaadin Flow。
我注意到很多人和例子都使用 Flows 作为 List<> 的包装器,例如像这样: @Query("SELECT * from some_model ORDER BY some_field") fun
Vaadin 突然停止构建我的库并出现以下错误。我已经跳了 Vaadin 舞(还有很多其他的东西),但我现在没主意了。我尝试为生产构建库(但对于开发也失败了)。 我正在使用 Vaadin Flow。
关闭。这个问题是opinion-based 。目前不接受答案。 想要改进这个问题吗?更新问题,以便 editing this post 可以用事实和引文来回答它。 . 已关闭 3 年前。 Improv
git flow init后,如何删除git flow模型? 如何从 .git/config 文件中删除所有相关配置? $ git flow init # force reset $ git flow
我运行了 git init 并在选择第一个分支时犯了一个错误。现在我想重新运行它来更改设置,但它再也不会问第一个问题。 Which branch should be used for bringing
我刚刚开始一份新工作,他们的代码管理一团乱。通常情况下这没什么问题,我可以应付,但在这个地方,情况就糟糕得离谱了。 他们使用 TFS...对此我无能为力。没有机会介绍 git,但我一直在阅读有关 gi
我的应用程序有更新问题。我不太明白 subview 之间的数据流是怎么回事。 这是我目前的结构 ViewModel:ObsebsrvableObject MainView 与 ObservedObje
为什么“flow check-contents”需要使用 < 将文件重定向到其中,而“flow suggest”则不需要?看起来 check-contents 应该假设命令行参数是要检查的文件路径。
最近我在 Git 中发现了工作流的三个概念: GitFlow GitHub 流程 GitLab 流程 我读过 the nice articles关于它,但我不太了解 GitLab Flow。 简单地说
我们刚刚改用 Hg Flow,但我们还没有弄清楚的一件事是如何最好地使用 Jenkins。理想情况下,我们将有一个构建和测试开发的作业,一个构建和测试默认作业和其他作业,这些作业在创建功能或发布分支时
将 Vaadin 12 与 FormLayout 一起使用和标签左侧的输入字段。 我想设置标签列的宽度。如何使用 Java API 实现这一点? 最佳答案 用于设置个人 FormItem标签宽度和/或
我正在使用 React-Flow 来可视化 React 中组件的树状层次结构。每当您在 React-Flow 中创建自定义节点时,您都可以像这样在树中使用它: ,我就可以做到这一点。 .有没有
我是一名优秀的程序员,十分优秀!