首页 > 其他分享 >417. Pacific Atlantic Water Flow[Medium]

417. Pacific Atlantic Water Flow[Medium]

时间:2023-02-24 18:55:31浏览次数:35  
标签:Medium Flow Pacific heights Atlantic Ocean col row

417. Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Constraints:

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 10^5

Example
image

Input: 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]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

思路

Pacific 是左面和上面,Atlantic 是右面和下面,利用深度遍历分别找出两种各自能流到的所有格子,最后的结果就是他们的交集

题解

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
       int row, col;
        HashSet<List<Integer>> pacificVisit = new HashSet<>();
        HashSet<List<Integer>> atlanticVisit = new HashSet<>();
        row = heights.length;
        col = heights[0].length;

        for (int i = 0; i < row; i++) {
	    // 左面
            dfsAtlanticPacific(i, 0, pacificVisit, heights[i][0], heights);
	    // 右面
            dfsAtlanticPacific(i, col - 1, atlanticVisit, heights[i][col - 1], heights);
        }

        for (int i = 0; i < col; i++) {
	    // 上面
            dfsAtlanticPacific(0, i, pacificVisit, heights[0][i], heights);
	    // 下面
            dfsAtlanticPacific(row - 1, i, atlanticVisit, heights[row - 1][i], heights);
        }
	// 找出交集
        return pacificVisit.stream().filter(atlanticVisit::contains).collect(Collectors.toList());
    }

    private void dfsAtlanticPacific(int row, int col, HashSet<List<Integer>> visit, int pre, int[][] heights) {
        if (row < 0 || row >= heights.length || col < 0 || col >= heights[0].length ||
		// 当前路径遍历过直接跳
                visit.contains(Arrays.asList(row, col)) ||
		// 这个条件很关键,如果上一个节点大于当前节点,因为整体遍历的趋势是从外往内的,里面的比外面小,就代表水无法往外流,那就跳过
                heights[row][col] < pre)
            return;

        visit.add(Arrays.asList(row, col));
        dfsAtlanticPacific(row + 1, col, visit, heights[row][col], heights);
        dfsAtlanticPacific(row - 1, col, visit, heights[row][col], heights);
        dfsAtlanticPacific(row, col + 1, visit, heights[row][col], heights);
        dfsAtlanticPacific(row, col - 1, visit, heights[row][col], heights);
    }

标签:Medium,Flow,Pacific,heights,Atlantic,Ocean,col,row
From: https://www.cnblogs.com/tanhaoo/p/17152787.html

相关文章

  • 133. Clone Graph[Medium]
    133.CloneGraphGivenareferenceofanodeinaconnectedundirectedgraph.Returnadeepcopy(clone)ofthegraph.Eachnodeinthegraphcontainsavalue......
  • 200. Number of Islands[Medium]
    200.NumberofIslandsGivenanmxn2Dbinarygridgridwhichrepresentsamapof'1's(land)and'0's(water),returnthenumberofislands.Anislandissu......
  • GIt Flow(一种git开发规范)
    一、前言gitflow是团队通过git进行合作的一种对代码进行管理的规范,主要作用是保证协同工作的顺利进行和代码的正常运行。二、概括规范中代码分为两大分支(dev、master),ma......
  • 用 Tensorflow.js 做了一个动漫分类的功能(一)
    前言:    浏览某乎网站时发现了一个分享各种图片的博主,于是我顺手就保存了一些。但是一张一张的保存实在太麻烦了,于是我就想要某虫的手段来处理。这样保存的确是很......
  • 用 Tensorflow.js 做了一个动漫分类的功能(二)
    前言:    前面已经通过采集拿到了图片,并且也手动对图片做了标注。接下来就要通过Tensorflow.js基于mobileNet训练模型,最后就可以实现在采集中对图片进行自动分......
  • tensorflow.js 对视频 / 直播人脸检测和特征点收集
    前言:    这里要介绍的是Tensorflow.js官方提供的两个人脸检测模型,分别是face-detection和face-landmarks-detection。他们不但可以对视频中的人间进行精确定......
  • tensorflow.js 多分类,机器学习区分企鹅种类
    前言:    在规则编码中,我们常常会遇到需要通过多种区间判断某种物品分类。比如二手物品的定价,尽管不是新品没有SKU但是基本的参数是少不了。想通过成色来区分某......
  • tensorflow.js 视频图片多目标检测
    前言:    Tensorflow.js官方提供了很多常用模型库,涵盖了平时开发中大部分场景的模型。例如,前面提到的图片识别,除此之外还有人体姿态识别,目标物体识别,语音文字等识......
  • tensorflow2.0+TF-lite 各种报错
    generic_type:type"InterpreterWrapper"isalreadyregistered!原因:tensorflow2.5.0rc0版本太高,降低版本:pipinstalltensorflow==2.3  ValueErron:"batch_si......
  • 我通过 tensorflow 预测了博客的粉丝数
    前言:     由于最近接触了tensorflow.js,出于试一下的心态,想通过线性回归预测一下博客的粉丝走向和数量,结果翻车了。虽然场景用错地方,但是整个实战方法用在身高体......