亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

leetcode200. Number of Islands

Zoom / 2579人閱讀

摘要：題目要求提供一個(gè)二維數(shù)組表示一張地圖，其中代表陸地，代表海洋。這里使用一個(gè)新的二維數(shù)組來(lái)表示對(duì)應(yīng)地圖上的元素屬于哪個(gè)并查集。在合并的時(shí)候先進(jìn)行判斷，如果二者為已經(jīng)相連的陸地，則無(wú)需合并，否則將新的二維數(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

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

思路一： union-find并查集

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

拋開(kāi)從二者判斷是否屬于同一個(gè)并查集，我們從遍歷的角度來(lái)看這個(gè)問(wèn)題。其實(shí)如果我們沒(méi)遇到一個(gè)陸地，就將屬于該陸地的所有領(lǐng)域都標(biāo)記為已經(jīng)遍歷過(guò)。那么下一次遇到一塊新陸地的時(shí)候，該陸地一定是屬于另一個(gè)版塊。這種算法可以通過(guò)深度優(yōu)先算法思想來(lái)實(shí)現(xiàn)。一旦遇到一塊陸地，就遞歸的對(duì)上下左右的領(lǐng)域進(jìn)行訪問(wèn)。該算法通過(guò)遞歸實(shí)現(xiàn)簡(jiǎ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);
    }



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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/70395.html

相關(guān)文章

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

    摘要：解題思路標(biāo)零法對(duì)這個(gè)矩陣進(jìn)行循環(huán)訪問(wèn)每一個(gè)點(diǎn)當(dāng)這個(gè)點(diǎn)等于，島嶼數(shù)量，與其同時(shí)用算法訪問(wèn)周?chē)钠渌c(diǎn)，進(jìn)行同樣的操作且將訪問(wèn)過(guò)且等于的點(diǎ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 評(píng)論0 收藏0

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

    摘要：兩個(gè)循環(huán)遍歷整個(gè)矩陣，出現(xiàn)則將其周?chē)噜彽娜繕?biāo)記為，用子函數(shù)遞歸標(biāo)記。注意里每次遞歸都要判斷邊界。寫(xiě)一個(gè)的，寫(xiě)熟練。 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 評(píng)論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 評(píng)論0 收藏0

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

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

    Raaabbit 評(píng)論0 收藏0

  • leetcode130. Surrounded Regions

    摘要：將所有和邊界相連的都標(biāo)記出來(lái)。那么當(dāng)我重新遍歷數(shù)組的時(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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<