力扣——417. 太平洋大西洋水流问题(Java、python、C代码实现)
2023-09-14 09:05:31 时间
- 太平洋大西洋水流问题
有一个 m × n 的矩形岛屿,与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界,而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights , heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多,如果相邻单元格的高度 小于或等于 当前单元格的高度,雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回 网格坐标 result 的 2D列表 ,其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。
示例 1:
输入: heights = [[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]]
示例 2:
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
python代码
class Solution:
def __init__(self):
self.result_all = None
# 分别表示上右下左
self.directs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
self.m = 0
self.n = 0
# 表示能流到太平洋
self.po = None
# 表示能流到大西洋
self.ao = None
self.visited = None
def pacificAtlantic(self, matrix) :
# 初始化一些东西
self.result_all = []
self.m = len(matrix)
if self.m == 0:
return self.result_all
self.n = len(matrix[0])
self.ao = [[0] * self.n for _ in range(self.m)]
self.po = [[0] * self.n for _ in range(self.m)]
self.visited = [[0] * self.n for _ in range(self.m)]
# 本题顺着流不太好做,我们用逆流的方式来思考
# 从上面的太平洋逆流
for i in range(0, 1):
for j in range(self.n):
self.dfs(matrix, i, j, True)
# 从左边的太平洋逆流
self.visited = [[0] * self.n for _ in range(self.m)]
for i in range(self.m):
for j in range(0, 1):
self.dfs(matrix, i, j, True)
# 下面的大西洋
self.visited = [[0] * self.n for _ in range(self.m)]
for i in range(self.m - 1, self.m):
for j in range(self.n):
self.dfs(matrix, i, j, False)
# 右边的大西洋
self.visited = [[0] * self.n for _ in range(self.m)]
for i in range(self.m):
for j in range(self.n -1, self.n):
self.dfs(matrix, i, j, False)
for i in range(self.m):
for j in range(self.n):
if self.po[i][j] == 1 and self.ao[i][j] == 1:
self.result_all.append((i, j))
return self.result_all
def dfs(self, matrix, x, y, flag):
if self.visited[x][y] == 1:
return
self.visited[x][y] = 1
if flag:
# 表示是太平洋
self.po[x][y] = 1
else:
# 表示是大西洋
self.ao[x][y] = 1
for i in range(4):
newx = x + self.directs[i][0]
newy = y + self.directs[i][1]
if not self.in_area(newx, newy):
continue
if matrix[x][y] > matrix[newx][newy]:
continue
self.dfs(matrix, newx, newy, flag)
return
def in_area(self, x, y):
return 0 <= x < self.m and 0 <= y < self.n
Java代码:
class Solution {
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int[][] heights;
int m, n;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
this.heights = heights;
this.m = heights.length;
this.n = heights[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(i, 0, pacific);
}
for (int j = 1; j < n; j++) {
dfs(0, j, pacific);
}
for (int i = 0; i < m; i++) {
dfs(i, n - 1, atlantic);
}
for (int j = 0; j < n - 1; j++) {
dfs(m - 1, j, atlantic);
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
List<Integer> cell = new ArrayList<Integer>();
cell.add(i);
cell.add(j);
result.add(cell);
}
}
}
return result;
}
public void dfs(int row, int col, boolean[][] ocean) {
if (ocean[row][col]) {
return;
}
ocean[row][col] = true;
for (int[] dir : dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
dfs(newRow, newCol, ocean);
}
}
}
}
C代码:
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
/*
对每个点dfs,如果能够同时走到(左 || 上) && (右 || 下), 就把这个点保存下来;
*/
int g_flag_p, g_flag_a;
int x_dir[4] = {0, 1, 0, -1};
int y_dir[4] = {1, 0, -1, 0};
int bk[201][202];
void dfs(int** heights, int x_size, int y_size, int x, int y)
{
int i;
int val = heights[x][y];
bk[x][y] = 1;
if (g_flag_p && g_flag_a) {
return;
}
if (y == 0 || x == 0)
g_flag_p = true;
if ((x == x_size - 1) || (y == y_size - 1))
g_flag_a = true;
for (i = 0; i < 4; i++) {
int _x = x + x_dir[i];
int _y = y + y_dir[i];
if (_x < 0 || _x >= x_size || _y < 0 || _y >= y_size || bk[_x][_y] == 1)
continue;
if (val >= heights[_x][_y])
dfs(heights, x_size, y_size, _x, _y);
}
}
int** pacificAtlantic(int** heights, int heightsSize, int* heightsColSize, int* returnSize, int** returnColumnSizes){
int max_len = heightsSize * (*heightsColSize);
int **res = malloc(sizeof(int *) * max_len);
int i, j;
(*returnColumnSizes) = malloc(sizeof(int) * max_len);
for (i = 0; i < max_len; i++) {
res[i] = malloc(sizeof(int) * 2);
(*returnColumnSizes)[i] = 2;
}
(*returnSize) = 0;
for (i = 0; i < heightsSize; i++) {
for (j = 0; j < (*heightsColSize); j++) {
g_flag_p = 0;
g_flag_a = 0;
memset(bk, 0, sizeof(bk));
dfs(heights, heightsSize, (*heightsColSize), i, j);
if (g_flag_p && g_flag_a) {
res[(*returnSize)][0] = i;
res[(*returnSize)++][1] = j;
}
}
}
return res;
}
作者:KJ.JK
本文仅用于交流学习,未经作者允许,禁止转载,更勿做其他用途,违者必究。
文章对你有所帮助的话,欢迎给个赞或者 star,你的支持是对作者最大的鼓励,不足之处可以在评论区多多指正,交流学习
相关文章
- Python实现将不规范的英文名字首字母大写
- python数据结构之图的实现方法
- Python每日一练(20230221)
- Atitit.http代理的实现 代码java php c# python
- paip.判断字符是否中文与以及判读是否是汉字uapi python java php
- paip.web数据绑定 下拉框的api设计 选择框 uapi python .net java swing jsf总结
- 华为OD机试 - 异常的打卡记录(Java & JS & Python)
- 华为OD机试 - 数字加减游戏(Java & JS & Python)
- 华为OD机试 - 机器人(Java & JS & Python)
- 华为OD机试 - 最大化控制资源成本(Java & JS & Python)
- 华为OD机试 - 真正的密码(Java & JS & Python)
- 华为OD机试 - ABR 车路协同场景(Java & JS & Python)
- 编程笔试(解析及代码实现):猴子吃桃。猴子第一天吃了若干个桃子,当即吃了一半,还不解馋,又多吃了一个…的C++、Java、Python、C#等语言代码实现
- 蓝桥杯官网 试题 PREV-111 历届真题 大胖子走迷宫【第十届】【决赛】【研究生组】【C++】【Java】【Python】三种解法
- 为什么大家都在学Python?Python学习难吗?
- 教你如何在Spark Scala/Java应用中调用Python脚本
- 【华为OD机试 2023】 日志首次上报最多积分(C++ Java JavaScript Python)
- 【华为OD机试 2023】 不含101的数(C++ Java JavaScript Python)
- 【华为OD机试 2023】 计算快递主站点(C++ Java JavaScript Python)
- 【 华为OD机试 2023】 静态扫描 / 采用合理的缓存策略,最少需要的金币数(C++ Java JavaScript Python)
- 【 华为OD机试 2023】新员工座位 / 统计友好度最大值(C++ Java JavaScript Python)
- Python编程:partial偏函数
- 华为校招机试 - 发广播(Java & JS & Python)