溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹golang刷leetcode 技巧之如何解決島嶼的最大面積問題，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
給定一個包含了一些 0 和 1 的非空二維數(shù)組 grid 。
一個 島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在水平或者豎直方向上相鄰。你可以假設 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]]
對于上面這個給定矩陣應返回 6。注意答案不應該是 11 ，因為島嶼只能包含水平或垂直的四個方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
對于上面這個給定的矩陣, 返回 0。
注意: 給定的矩陣grid 的長度和寬度都不超過 50。
解題思路：
1，這個問題和朋友圈那個問題類似，只不過求解目標不一樣
2，朋友圈問題是求解連通域個數(shù)，這里是求解聯(lián)通域面積
3，解決方案：深度優(yōu)先遍歷
4，深度優(yōu)先遍歷最簡單的方法便是遞歸
5，這里比朋友圈問題復雜的地方在于，朋友圈問題是對稱的，因此是個一維問題，這個問題是二維問題
6，小技巧：是否訪問一般用map存，當時golang訪問map需要判定，所以簡單方法用slice存
代碼實現(xiàn)：
func maxAreaOfIsland(grid [][]int) int {visited:=make([][]int,len(grid))for i:=0;i<len(grid);i++{visited[i]=make([]int,len(grid[0]))}max:=0for i:=0;i<len(grid);i++{for j:=0;j<len(grid[0]);j++{v:=dfs(grid,visited,i,j)if v>max{max=v}}}return max}func dfs(grid,visited [][]int,i,j int)int{if i<0 ||j<0 ||i>=len(grid) ||j>=len(grid[0]) ||grid[i][j]!=1 ||visited[i][j]==1{return 0}visited[i][j]=1return 1+dfs(grid,visited,i+1,j)+dfs(grid,visited,i,j+1)+dfs(grid,visited,i-1,j)+dfs(grid,visited,i,j-1)}
以上是“golang刷leetcode 技巧之如何解決島嶼的最大面積問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關知識，歡迎關注億速云行業(yè)資訊頻道！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
