資訊專欄INFORMATION COLUMN
摘要：找到給定的二維數(shù)組中最大的島嶼面積。思路給定一個由和組成的二維數(shù)組，其中代表島嶼土地，要求找出二維數(shù)組中最大的島嶼面積，沒有則返回。樣例如樣例所示，二維數(shù)組的最大島嶼面積為，下面來講解深度優(yōu)先搜索的做法。
給定一個包含了一些 0 和 1 的非空二維數(shù)組 grid 。
一個 島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個 1 必須在水平或者豎直方向上相鄰。你可以假設(shè) grid的四個邊緣都被 0（代表水）包圍著。
找到給定的二維數(shù)組中最大的島嶼面積。(如果沒有島嶼，則返回面積為 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]]對于上面這個給定矩陣應(yīng)返回 6。注意答案不應(yīng)該是 11 ，因為島嶼只能包含水平或垂直的四個方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]對于上面這個給定的矩陣, 返回 0。
注意: 給定的矩陣grid 的長度和寬度都不超過 50。
(DFS) O ( n ? m ) O(n*m) O(n?m)
給定一個由0和1組成的二維數(shù)組grid，其中1代表島嶼土地，要求找出二維數(shù)組中最大的島嶼面積，沒有則返回0。
樣例：
如樣例所示，二維數(shù)組grid的最大島嶼面積為4，下面來講解深度優(yōu)先搜索的做法。
我們定義這樣一種搜索順序，即先搜索島嶼上的某塊土地，然后以4個方向向四周探索與之相連的每一塊土地，搜索過程中維護(hù)一個area變量，用來記錄搜索過的土地總數(shù)。為了避免重復(fù)搜索，在這個過程中需要將已經(jīng)搜索過的土地置為0，最后我們返回最大的area即可。
搜索函數(shù)設(shè)計：
int dfs(int x, int y)x，y是當(dāng)前搜索到的二維數(shù)組grid的橫縱坐標(biāo)。
實現(xiàn)細(xì)節(jié)：
grid以及二維數(shù)組的行數(shù)n和列數(shù)m都定義為全局變量可以減少搜索函數(shù)dfs的參數(shù)數(shù)量。具體過程如下：
res = 0，遍歷grid數(shù)組。grid數(shù)組元素grid[i][j] == 1，也就是說為土地的話，就以當(dāng)前土地(i,j)為起點繼續(xù)向四周搜索聯(lián)通的土地。area中。res = max(res,area),不斷更新答案。時間復(fù)雜度分析： O ( n ? m ) O(n*m) O(n?m)， n n n是二維數(shù)組的行數(shù)， m m m是二維數(shù)組的列數(shù)，每個位置只被搜索一次。
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)搜索過，標(biāo)記為0 for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; //當(dāng)前土地未出界也未被搜索過，繼續(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; }};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)搜索過，標(biāo)記為0 for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; //當(dāng)前土地未出界也未被搜索過，繼續(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://hztianpu.com/yun/119113.html
摘要：示例輸入輸出示例輸入輸出示例輸入輸出示例輸入輸出思路貪心給定一組非負(fù)數(shù)，重新排列使其組成一個最大的整數(shù)。具體過程如下自定義排序規(guī)則函數(shù)，將數(shù)組按照自定義排序規(guī)則重新排序。時間復(fù)雜度分析排序的時間復(fù)雜度為。 ...
摘要：給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下，今晚能夠偷竊到的最高金額。狀態(tài)表示表示偷竊號到號房間所能獲得的最高金額。下標(biāo)均從開始打家劫舍我們已經(jīng)知道了房間單排排列的狀態(tài)轉(zhuǎn)移方程，接下來思考房間環(huán)狀排列的做法。 ...
摘要：返回注意答案并不是因為陸地相連要求必須是在上下左右四個方向。返回應(yīng)為想法我們還是要遍歷數(shù)組中的每一個元素。如果數(shù)組元素值為，則我們以這個值為起點進(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...
摘要：題目鏈接題目分析給定一組坐標(biāo)，返回能組成面積最大的三角形面積。思路只能套循環(huán)了。利用三邊求面積公式得面積。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D77 812. Largest Triangle Area 題目鏈接 812. Largest Triangle Area 題目分析 給定一組坐標(biāo)，返回能組成面積最大的三角形面積。 思路 只能套for循環(huán)了。利用三邊求面積公式得面...
摘要：思路從題目解析可以得知，每一面每一行或每一列取最大值相加即可。傳進(jìn)來的是一個二維數(shù)組。固定時二維數(shù)組的第個元素代表時，的值軸的間隔為第個元素代表時，的值。計算二維數(shù)組每一個元素中，相同位置的值的最高值即可。 883. Projection Area of 3D Shapes 題目鏈接 883. Projection Area of 3D Shapes 題目分析 這個題目要求計算一個三維...
閱讀 624·2021-11-25 09:44
閱讀 2790·2021-11-24 09:39
閱讀 2413·2021-11-22 15:29
閱讀 3654·2021-11-15 11:37
閱讀 3545·2021-09-24 10:36
閱讀 2627·2021-09-04 16:41
閱讀 1136·2021-09-03 10:28
閱讀 2037·2019-08-30 15:55
