成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode200. Number of Islands

Zoom / 2526人閱讀

摘要：題目要求提供一個二維數(shù)組表示一張地圖，其中代表陸地，代表海洋。這里使用一個新的二維數(shù)組來表示對應(yīng)地圖上的元素屬于哪個并查集。在合并的時候先進(jìn)行判斷，如果二者為已經(jīng)相連的陸地，則無需合并，否則將新的二維數(shù)組上的元素指向所在的并查集。

題目要求 
Given a 2d grid map of "1"s (land) and "0"s (water), count the number of islands. 
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. 
You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

提供一個二維數(shù)組表示一張地圖，其中1代表陸地，0代表海洋。問在這張地圖上一共有幾個陸地.

思路一： union-find并查集

這道題目從經(jīng)典的數(shù)據(jù)結(jié)構(gòu)的角度來說可以使用并查集來進(jìn)行判斷，將每一個海洋看做一個集合合并起來，將相鄰的陸地通過并查集連接起來。最后查看并查集中剩余下的集合數(shù)。
這里使用一個新的二維數(shù)組來表示對應(yīng)地圖上的元素屬于哪個并查集。在合并的時候先進(jìn)行判斷，如果二者為已經(jīng)相連的陸地，則無需合并，否則將新的二維數(shù)組上的元素指向所在的并查集。

int row;
    int column;
    char[][] grid;
    int count;
    int[][] tempRegion;
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0){
            return 0;
        }
        
        this.grid = grid;
        this.row = grid.length;
        this.column = grid[0].length;
        this.count = row * column; 
        this.tempRegion = new int[row][column];

        for(int i = 0 ; i
思路二：深度優(yōu)先搜索

拋開從二者判斷是否屬于同一個并查集，我們從遍歷的角度來看這個問題。其實如果我們沒遇到一個陸地，就將屬于該陸地的所有領(lǐng)域都標(biāo)記為已經(jīng)遍歷過。那么下一次遇到一塊新陸地的時候，該陸地一定是屬于另一個版塊。這種算法可以通過深度優(yōu)先算法思想來實現(xiàn)。一旦遇到一塊陸地，就遞歸的對上下左右的領(lǐng)域進(jìn)行訪問。該算法通過遞歸實現(xiàn)簡潔高效！


    public int numIslands2(char[][] grid){
        if(grid==null || grid.length==0 || grid[0].length==0) return 0;
        this.row = grid.length;
        this.column = grid[0].length;
        int count = 0;
        for(int i = 0 ; irow || j<0 || j>column || grid[i][j] != "1") return;
        grid[i][j] = "X";
        merge(grid, i-1, j);
        merge(grid, i+1, j);
        merge(grid, i, j-1);
        merge(grid, i, j+1);
    }



想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70395.html

相關(guān)文章

  • [Leetcode] Number of Islands 島嶼數(shù)量（JavaScript 實現(xiàn)）

    摘要：解題思路標(biāo)零法對這個矩陣進(jìn)行循環(huán)訪問每一個點當(dāng)這個點等于，島嶼數(shù)量，與其同時用算法訪問周圍的其他點，進(jìn)行同樣的操作且將訪問過且等于的點標(biāo)記為零。版本島嶼數(shù)量搜索右邊搜索左邊搜索下邊搜索上邊 Q: Number of Islands Given a 2d grid map of 1s (land) and 0s (water), count the number of islands. ...

    pingan8787 評論0 收藏0

  • [LeetCode/LintCode] Number of Islands [DFS]

    摘要：兩個循環(huán)遍歷整個矩陣，出現(xiàn)則將其周圍相鄰的全部標(biāo)記為，用子函數(shù)遞歸標(biāo)記。注意里每次遞歸都要判斷邊界。寫一個的，寫熟練。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...

    Fourierr 評論0 收藏0

  • [LeetCode] 694. Number of Distinct Islands

    Problem Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are s...

    SunZhaopeng 評論0 收藏0

  • [Leetcode] Number of Islands 島嶼個數(shù)

    摘要：同時我們每找到一個，就將其標(biāo)為，這樣就能把整個島嶼變成。我們只要記錄對矩陣遍歷時能進(jìn)入多少次搜索，就代表有多少個島嶼。 Number of Islands 最新更新的思路，以及題II的解法請訪問：https://yanjia.me/zh/2018/11/... Given a 2d grid map of 1s (land) and 0s (water), count the nu...

    Raaabbit 評論0 收藏0

  • leetcode130. Surrounded Regions

    摘要：將所有和邊界相連的都標(biāo)記出來。那么當(dāng)我重新遍歷數(shù)組的時候，剩下的則是被完全包圍的。 題目要求 Given a 2D board containing X and O (the letter O), capture all regions surrounded by X. A region is captured by flipping all Os into Xs in that s...

    focusj 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<