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

資訊專欄INFORMATION COLUMN

LeetCode 695. 島嶼的最大面積【c++/java詳細(xì)題解】

MangoGoing / 2529人閱讀

摘要：找到給定的二維數(shù)組中最大的島嶼面積。思路給定一個(gè)由和組成的二維數(shù)組，其中代表島嶼土地，要求找出二維數(shù)組中最大的島嶼面積，沒(méi)有則返回。樣例如樣例所示，二維數(shù)組的最大島嶼面積為，下面來(lái)講解深度優(yōu)先搜索的做法。

1、題目

給定一個(gè)包含了一些 0 和 1 的非空二維數(shù)組 grid 。

一個(gè) 島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個(gè) 1 必須在水平或者豎直方向上相鄰。你可以假設(shè) grid的四個(gè)邊緣都被 0（代表水）包圍著。

找到給定的二維數(shù)組中最大的島嶼面積。(如果沒(méi)有島嶼，則返回面積為 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]

對(duì)于上面這個(gè)給定矩陣應(yīng)返回 6。注意答案不應(yīng)該是 11 ，因?yàn)閸u嶼只能包含水平或垂直的四個(gè)方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]

對(duì)于上面這個(gè)給定的矩陣, 返回 0。

注意: 給定的矩陣grid 的長(zhǎng)度和寬度都不超過(guò) 50。

2、思路

(DFS) O ( n ? m ) O(n*m) O(n?m)

給定一個(gè)由0和1組成的二維數(shù)組grid，其中1代表島嶼土地，要求找出二維數(shù)組中最大的島嶼面積，沒(méi)有則返回0。

樣例：

如樣例所示，二維數(shù)組grid的最大島嶼面積為4，下面來(lái)講解深度優(yōu)先搜索的做法。

我們定義這樣一種搜索順序，即先搜索島嶼上的某塊土地，然后以4個(gè)方向向四周探索與之相連的每一塊土地，搜索過(guò)程中維護(hù)一個(gè)area變量，用來(lái)記錄搜索過(guò)的土地總數(shù)。為了避免重復(fù)搜索，在這個(gè)過(guò)程中需要將已經(jīng)搜索過(guò)的土地置為0，最后我們返回最大的area即可。

搜索函數(shù)設(shè)計(jì)：

int dfs(int x, int y)

x，y是當(dāng)前搜索到的二維數(shù)組grid的橫縱坐標(biāo)。

實(shí)現(xiàn)細(xì)節(jié)：

  • 1、為了確保每個(gè)位置只被搜索一次，從當(dāng)前搜索過(guò)的位置繼續(xù)搜索下一個(gè)位置時(shí)，需要對(duì)當(dāng)前位置進(jìn)行標(biāo)識(shí)，表示已經(jīng)被搜索。
  • 2、將二維數(shù)組grid以及二維數(shù)組的行數(shù)n和列數(shù)m都定義為全局變量可以減少搜索函數(shù)dfs的參數(shù)數(shù)量。
  • 3、使用偏移數(shù)組來(lái)簡(jiǎn)化代碼，如下圖所示：

具體過(guò)程如下：

  • 1、定義res = 0，遍歷grid數(shù)組。
  • 2、如果當(dāng)前grid數(shù)組元素grid[i][j] == 1，也就是說(shuō)為土地的話，就以當(dāng)前土地(i,j)為起點(diǎn)繼續(xù)向四周搜索聯(lián)通的土地。
  • 3、直到搜索完當(dāng)前土地的所有的連通土地，最后將連通土地總數(shù)記錄到area中。
  • 4、執(zhí)行res = max(res,area),不斷更新答案。

時(shí)間復(fù)雜度分析： O ( n ? m ) O(n*m) O(n?m)， n n n是二維數(shù)組的行數(shù)， m m m是二維數(shù)組的列數(shù)，每個(gè)位置只被搜索一次。

3、c++代碼

class Solution {public:    int n, m;    vector<vector<int>>g;    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //偏移數(shù)組    int dfs(int x, int y) //搜索函數(shù)    {        int area = 1;        g[x][y] = 0;  //已經(jīng)搜索過(guò)，標(biāo)記為0        for(int i = 0; i < 4; i++)        {            int a = x + dx[i], b = y + dy[i];            //當(dāng)前土地未出界也未被搜索過(guò)，繼續(xù)下一層搜索            if(a >=0 && a < n && b >=0 && b < m && g[a][b])                area += dfs(a, b);        }              return area; //返回連通土地總數(shù)    }    int maxAreaOfIsland(vector<vector<int>>& grid) {        g = grid;        int res = 0;        n = grid.size(), m = grid[0].size();        for(int i = 0; i < n; i++)            for(int j = 0; j < m; j++)                if(g[i][j])                    res = max(res,dfs(i,j));        return res;                    }};

4、java代碼

class Solution {    private int n, m;    private int[][] g;    private int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};//偏移數(shù)組    public int dfs(int x, int y) //搜索函數(shù)    {        int area = 1;        g[x][y] = 0; //已經(jīng)搜索過(guò)，標(biāo)記為0        for(int i = 0; i < 4; i++)        {            int a = x + dx[i], b = y + dy[i];            //當(dāng)前土地未出界也未被搜索過(guò)，繼續(xù)下一層搜索            if(a >=0 && a < n && b >= 0 && b < m && g[a][b] != 0)                area += dfs(a, b);        }              return area; //返回連通土地總數(shù)    }    public int maxAreaOfIsland(int[][] grid) {        g = grid;        int res = 0;        n = grid.length; m = grid[0].length;        for(int i = 0; i < n; i++)            for(int j = 0; j < m; j++)                if(g[i][j] != 0)                    res = Math.max(res,dfs(i,j));        return res;      }}

原題鏈接： 695. 島嶼的最大面積

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

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

相關(guān)文章

  • LeetCode 179. 最大數(shù)【c++/java詳細(xì)題解】

    摘要：示例輸入輸出示例輸入輸出示例輸入輸出示例輸入輸出思路貪心給定一組非負(fù)數(shù)，重新排列使其組成一個(gè)最大的整數(shù)。具體過(guò)程如下自定義排序規(guī)則函數(shù)，將數(shù)組按照自定義排序規(guī)則重新排序。時(shí)間復(fù)雜度分析排序的時(shí)間復(fù)雜度為。 ...

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

  • LeetCode 213. 打家劫舍 II【c++/java詳細(xì)題解】

    摘要：給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，今晚能夠偷竊到的最高金額。狀態(tài)表示表示偷竊號(hào)到號(hào)房間所能獲得的最高金額。下標(biāo)均從開(kāi)始打家劫舍我們已經(jīng)知道了房間單排排列的狀態(tài)轉(zhuǎn)移方程，接下來(lái)思考房間環(huán)狀排列的做法。 ...

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

  • leetcode 695 Max Area of Island

    摘要：返回注意答案并不是因?yàn)殛懙叵噙B要求必須是在上下左右四個(gè)方向。返回應(yīng)為想法我們還是要遍歷數(shù)組中的每一個(gè)元素。如果數(shù)組元素值為，則我們以這個(gè)值為起點(diǎn)進(jìn)行深度優(yōu)先搜索。 題目詳情 Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-di...

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

  • Leetcode PHP題解--D77 812. Largest Triangle Area

    摘要：題目鏈接題目分析給定一組坐標(biāo)，返回能組成面積最大的三角形面積。思路只能套循環(huán)了。利用三邊求面積公式得面積。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D77 812. Largest Triangle Area 題目鏈接 812. Largest Triangle Area 題目分析 給定一組坐標(biāo)，返回能組成面積最大的三角形面積。 思路 只能套for循環(huán)了。利用三邊求面積公式得面...

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

  • Leetcode PHP題解--D17 883. Projection Area of 3D Sha

    摘要：思路從題目解析可以得知，每一面每一行或每一列取最大值相加即可。傳進(jìn)來(lái)的是一個(gè)二維數(shù)組。固定時(shí)二維數(shù)組的第個(gè)元素代表時(shí)，的值軸的間隔為第個(gè)元素代表時(shí)，的值。計(jì)算二維數(shù)組每一個(gè)元素中，相同位置的值的最高值即可。 883. Projection Area of 3D Shapes 題目鏈接 883. Projection Area of 3D Shapes 題目分析 這個(gè)題目要求計(jì)算一個(gè)三維...

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

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

0條評(píng)論

閱讀需要支付1元查看
<