leetcode200. Number of Islands

Zoom 發布于2019-08-16 10:45 / 2518人閱讀

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

題目要求

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

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

思路一： union-find并查集

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

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
思路二：深度優先搜索
拋開從二者判斷是否屬于同一個并查集，我們從遍歷的角度來看這個問題。其實如果我們沒遇到一個陸地，就將屬于該陸地的所有領域都標記為已經遍歷過。那么下一次遇到一塊新陸地的時候，該陸地一定是屬于另一個版塊。這種算法可以通過深度優先算法思想來實現。一旦遇到一塊陸地，就遞歸的對上下左右的領域進行訪問。該算法通過遞歸實現簡潔高效！
    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);
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Islands Leetcod LeetCode LeetCode_String

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

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

[Leetcode] Number of Islands 島嶼數量（JavaScript 實現）

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

pingan8787 2019-08-23 12:10 評論0 收藏0
[LeetCode/LintCode] Number of Islands [DFS]

摘要：兩個循環遍歷整個矩陣，出現則將其周圍相鄰的全部標記為，用子函數遞歸標記。注意里每次遞歸都要判斷邊界。寫一個的，寫熟練。 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 2019-08-14 15:15 評論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 2019-08-16 13:50 評論0 收藏0
[Leetcode] Number of Islands 島嶼個數

摘要：同時我們每找到一個，就將其標為，這樣就能把整個島嶼變成。我們只要記錄對矩陣遍歷時能進入多少次搜索，就代表有多少個島嶼。 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 2019-08-14 12:32 評論0 收藏0
leetcode130. Surrounded Regions

摘要：將所有和邊界相連的都標記出來。那么當我重新遍歷數組的時候，剩下的則是被完全包圍的。題目要求 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 2019-08-16 10:45 評論0 收藏0