力扣(LeetCode)417

qylost 發布于2019-08-16 15:06 / 1395人閱讀

摘要：太平洋處于大陸的左邊界和上邊界，而大西洋處于大陸的右邊界和下邊界。請找出那些水流既可以流動到太平洋，又能流動到大西洋的陸地單元的坐標。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一個 m x n 的非負整數矩陣來表示一片大陸上各個單元格的高度。“太平洋”處于大陸的左邊界和上邊界，而“大西洋”處于大陸的右邊界和下邊界。

規定水流只能按照上、下、左、右四個方向流動，且只能從高到低或者在同等高度上流動。

請找出那些水流既可以流動到“太平洋”，又能流動到“大西洋”的陸地單元的坐標。

解答：
反向思維，某個地方可以流向大西洋或太平洋，我們把它理解為太平洋或者大西洋可以流向某個區域，這樣一來只需要從大西洋或者太平樣的節點進行深度優先搜索即可。只不過原來的流動條件是高往低流，現在變為低往高流。
java ac代碼：

class Solution {
    
            
    boolean[][]left;
    boolean[][]right;
    boolean[][] flag1;
    boolean[][] flag2;
    
    public List pacificAtlantic(int[][] matrix) {
        List ans = new ArrayList(1000);
        if(matrix.length == 0)return ans;
        
        left = new boolean[matrix.length][matrix[0].length];
        right = new boolean[matrix.length][matrix[0].length];
        flag1 = new boolean[matrix.length][matrix[0].length];
        flag2 = new boolean[matrix.length][matrix[0].length];
        
        
        for(int i = 0;i < matrix.length;i++)
        {
            dfsleft(matrix,flag1,i,0);
            dfsright(matrix,flag2,i,matrix[0].length-1);
        }
        for(int i = 0;i < matrix[0].length;i++)
        {
            dfsleft(matrix,flag1,0,i);
            dfsright(matrix,flag2,matrix.length-1,i);
        }
        for(int i = 0;i < matrix.length;i++)
            for(int j = 0;j < matrix[0].length;j++)
                if(left[i][j] && right[i][j])
                    ans.add(new int[]{i,j});
        return ans;
        
    }
    
    void dfsleft(int[][] matrix,boolean[][]flag,int x,int y)
    {
        if(flag[x][y])return;
        flag[x][y] = true;
        left[x][y] = true;
        if((x-1 >= 0 && x-1 < matrix.length && y >= 0 && y< matrix[0].length) && matrix[x-1][y] >= matrix[x][y])
            dfsleft(matrix,flag,x-1,y);
        if((x+1 >= 0 && x+1 < matrix.length && y >= 0 && y< matrix[0].length) && matrix[x+1][y] >= matrix[x][y])
            dfsleft(matrix,flag,x+1,y);
        if((x >= 0 && x < matrix.length && y-1 >= 0 && y-1< matrix[0].length) && matrix[x][y-1] >= matrix[x][y])
            dfsleft(matrix,flag,x,y-1);
        if((x >= 0 && x < matrix.length && y+1 >= 0 && y+1< matrix[0].length) && matrix[x][y+1] >= matrix[x][y])
            dfsleft(matrix,flag,x,y+1);
    }
    
    
    void dfsright(int[][] matrix,boolean[][]flag,int x,int y)
    {
        if(flag[x][y])return;
        flag[x][y] = true;

        right[x][y] = true;
        if((x-1 >= 0 && x-1 < matrix.length && y >= 0 && y< matrix[0].length) && matrix[x-1][y] >= matrix[x][y])
            dfsright(matrix,flag,x-1,y);
        if((x+1 >= 0 && x+1 < matrix.length && y >= 0 && y< matrix[0].length) && matrix[x+1][y] >= matrix[x][y])
            dfsright(matrix,flag,x+1,y);
        if((x >= 0 && x < matrix.length && y-1 >= 0 && y-1< matrix[0].length) && matrix[x][y-1] >= matrix[x][y])
            dfsright(matrix,flag,x,y-1);
        if((x >= 0 && x < matrix.length && y+1 >= 0 && y+1< matrix[0].length) && matrix[x][y+1] >= matrix[x][y])
            dfsright(matrix,flag,x,y+1);
    }
    
    
    
}

云服務器 GPU云服務器力扣 LeetCode 服務器請求417 pdf417條形碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73270.html

力扣(LeetCode)310

摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節點。因此使用一個數組代表每個節點的入度，若入度為就是葉子節點。題目地址：https://leetcode-cn.com/probl...題目描述：對于一個具有樹特征的無向圖，我們可選擇任何一個節點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...

amuqiao 2019-08-16 16:13 評論0 收藏0
＜LeetCode天梯＞Day026 反轉鏈表（遞歸法+（迭代法）雙鏈表法） | 初級算法 | Py

摘要：關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無所住而生...

imingyu 2021-11-17 09:33 評論0 收藏0
力扣(LeetCode)452

摘要：對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。可以射出的弓箭的數量沒有限制。弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量。解答這是一道區間覆蓋問題，不太好說清楚，利用模板即可。題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方...

fanux 2019-08-16 15:20 評論0 收藏0
＜LeetCode天梯＞Day031 驗證二叉搜索樹（遞歸+中序遍歷） | 初級算法 | Pytho

摘要：有效二叉搜索樹定義如下節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值，根節點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 評論0 收藏0