讀完本文 ,可以去力扣解決如下題目: 200.島嶼數(shù)量(中等 )
1254.統(tǒng)計封閉島嶼的數(shù)目( 中等 )
1020.飛地的數(shù)量( 中等 )
1905.統(tǒng)計子島嶼( 中等 )
694.不同的島嶼數(shù)量( 中等 )
島嶼問題是經(jīng)典的面試高頻題,雖然基本的島嶼問題并不難,但是島嶼問題有一些有意思的擴展,比如求子島嶼數(shù)量,求形狀不同的島嶼數(shù)量等等,本文就來把這些問題一網(wǎng)打盡。
島嶼系列問題的核心考點就是用 DFS/BFS 算法遍歷二維數(shù)組。
本文主要來講解如何用 DFS 算法來秒殺島嶼系列問題,不過用 BFS 算法的核心思路是完全一樣的,無非就是把 DFS 改寫成 BFS 而已。
那么如何在二維矩陣中使用 DFS 搜索呢?如果你把二維矩陣中的每一個位置看做一個節(jié)點,這個節(jié)點的上下左右四個位置就是相鄰節(jié)點,那么整個矩陣就可以抽象成一幅網(wǎng)狀的「圖」結(jié)構(gòu)。
根據(jù)學習數(shù)據(jù)結(jié)構(gòu)和算法的框架思維,完全可以根據(jù)二叉樹的遍歷框架改寫出二維矩陣的 DFS 代碼框架:
// 二叉樹遍歷框架
void traverse (TreeNode root) {
traverse(root.left);
traverse(root.right);
}
// 二維矩陣遍歷框架
void dfs (int [][] grid, int i, int j, boolean [] visited) {
int m = grid.length, n = grid[
0 ].length;
if (i <
0 || j <
0 || i >= m || j >= n) {
// 超出索引邊界
return ;
}
if (visited[i][j]) {
// 已遍歷過 (i, j)
return ;
}
// 前序:進入節(jié)點 (i, j)
visited[i][j] =
true ;
dfs(grid, i -
1 , j);
// 上
dfs(grid, i
1 , j);
// 下
dfs(grid, i, j -
1 );
// 左
dfs(grid, i, j
1 );
// 右
// 后序:離開節(jié)點 (i, j)
// visited[i][j] =
true ;
}
因為二維矩陣本質(zhì)上是一幅「圖」,所以遍歷的過程中需要一個visited布爾數(shù)組防止走回頭路,如果你能理解上面這段代碼,那么搞定所有島嶼問題都很簡單。
這里額外說一個處理二維數(shù)組的常用小技巧,你有時會看到使用「方向數(shù)組」來處理上下左右的遍歷,和圖遍歷框架的代碼很類似:
// 方向數(shù)組,分別代表上、下、左、右
int [][] dirs =
new int [][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
void dfs (int [][] grid, int i, int j, boolean [] visited) {
int m = grid.length, n = grid[
0 ].length;
if (i <
0 || j <
0 || i >= m || j >= n) {
// 超出索引邊界
return ;
}
if (visited[i][j]) {
// 已遍歷過 (i, j)
return ;
}
// 進入節(jié)點 (i, j)
visited[i][j] =
true ;
// 遞歸遍歷上下左右的節(jié)點
for (
int [] d : dirs) {
int next_i = i d[
0 ];
int next_j = j d[
1 ];
dfs(grid, next_i, next_j);
}
// 離開節(jié)點 (i, j)
// visited[i][j] =
true ;
}
這種寫法無非就是用 for 循環(huán)處理上下左右的遍歷罷了,你可以按照個人喜好選擇寫法。
島嶼數(shù)量
這是力扣第 200 題「島嶼數(shù)量」,最簡單也是最經(jīng)典的一道島嶼問題,題目會輸入一個二維數(shù)組grid,其中只包含0或者1,0代表海水,1代表陸地,且假設(shè)該矩陣四周都是被海水包圍著的。
我們說連成片的陸地形成島嶼,那么請你寫一個算法,計算這個矩陣grid中島嶼的個數(shù),函數(shù)簽名如下:
int numIslands (char [][] grid) ;
比如說題目給你輸入下面這個grid有四片島嶼,算法應該返回 4:
思路很簡單,關(guān)鍵在于如何尋找并標記「島嶼」,這就要 DFS 算法發(fā)揮作用了,我們直接看解法代碼:
// 主函數(shù),計算島嶼數(shù)量
int numIslands (char [][] grid) {
int res = 0 ;
int m = grid.length, n = grid[0 ].length;
// 遍歷 grid
for (int i = 0 ; i < m; i ) {
for (int j = 0 ; j < n; j ) {
if (grid[i][j] == '1' ) {
// 每發(fā)現(xiàn)一個島嶼,島嶼數(shù)量加一
res ;
// 然后使用 DFS 將島嶼淹了
dfs(grid, i, j);
}
}
}
return res;
}
// 從 (i, j) 開始,將與之相鄰的陸地都變成海水
void dfs (char [][] grid, int i, int j) {
int m = grid.length, n = grid[0 ].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引邊界
return ;
}
if (grid[i][j] == '0' ) {
// 已經(jīng)是海水了
return ;
}
// 將 (i, j) 變成海水
grid[i][j] = '0' ;
// 淹沒上下左右的陸地
dfs(grid, i 1 , j);
dfs(grid, i, j 1 );
dfs(grid, i - 1 , j);
dfs(grid, i, j - 1 );
}
為什么每次遇到島嶼,都要用 DFS 算法把島嶼「淹了」呢?主要是為了省事,避免維護visited數(shù)組。
因為dfs函數(shù)遍歷到值為0的位置會直接返回,所以只要把經(jīng)過的位置都設(shè)置為0,就可以起到不走回頭路的作用。
PS:這類 DFS 算法還有個別名叫做 FloodFill 算法,現(xiàn)在有沒有覺得 FloodFill 這個名字還挺貼切的~
這個最最基本的島嶼問題就說到這,我們來看看后面的題目有什么花樣。
封閉島嶼的數(shù)量
上一題說二維矩陣四周可以認為也是被海水包圍的,所以靠邊的陸地也算作島嶼。
力扣第 1254 題「統(tǒng)計封閉島嶼的數(shù)目」和上一題有兩點不同:
1、用0表示陸地,用1表示海水。
2、讓你計算「封閉島嶼」的數(shù)目。所謂「封閉島嶼」就是上下左右全部被1包圍的0,也就是說靠邊的陸地不算作「封閉島嶼」。
函數(shù)簽名如下:
int closedIsland (int [][] grid)
比如題目給你輸入如下這個二維矩陣:
算法返回 2,只有圖中灰色部分的0是四周全都被海水包圍著的「封閉島嶼」。
那么如何判斷「封閉島嶼」呢?其實很簡單,把上一題中那些靠邊的島嶼排除掉,剩下的不就是「封閉島嶼」了嗎?
有了這個思路,就可以直接看代碼了,注意這題規(guī)定0表示陸地,用1表示海水:
// 主函數(shù):計算封閉島嶼的數(shù)量
int closedIsland (int [][] grid) {
int m = grid.length, n = grid[0 ].length;
for (int j = 0 ; j < n; j ) {
// 把靠上邊的島嶼淹掉
dfs(grid, 0 , j);
// 把靠下邊的島嶼淹掉
dfs(grid, m - 1 , j);
}
for (int i = 0 ; i < m; i ) {
// 把靠左邊的島嶼淹掉
dfs(grid, i, 0 );
// 把靠右邊的島嶼淹掉
dfs(grid, i, n - 1 );
}
// 遍歷 grid,剩下的島嶼都是封閉島嶼
int res = 0 ;
for (int i = 0 ; i < m; i ) {
for (int j = 0 ; j < n; j ) {
if (grid[i][j] == 0 ) {
res ;
dfs(grid, i, j);
}
}
}
return res;
}
// 從 (i, j) 開始,將與之相鄰的陸地都變成海水
void dfs (int [][] grid, int i, int j) {
int m = grid.length, n = grid[0 ].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
return ;
}
if (grid[i][j] == 1 ) {
// 已經(jīng)是海水了
return ;
}
// 將 (i, j) 變成海水
grid[i][j] = 1 ;
// 淹沒上下左右的陸地
dfs(grid, i 1 , j);
dfs(grid, i, j 1 );
dfs(grid, i - 1 , j);
dfs(grid, i, j - 1 );
}
只要提前把靠邊的陸地都淹掉,然后算出來的就是封閉島嶼了。
PS:處理這類島嶼問題除了 DFS/BFS 算法之外,Union Find 并查集算法也是一種可選的方法。
這道島嶼題目的解法稍微改改就可以解決力扣第 1020 題「飛地的數(shù)量」,這題不讓你求封閉島嶼的數(shù)量,而是求封閉島嶼的面積總和。
其實思路都是一樣的,先把靠邊的陸地淹掉,然后去數(shù)剩下的陸地數(shù)量就行了,注意第 1020 題中1代表陸地,0代表海水:
int numEnclaves (int [][] grid) {
int m = grid.length, n = grid[0 ].length;
// 淹掉靠邊的陸地
for (int i = 0 ; i < m; i ) {
dfs(grid, i, 0 );
dfs(grid, i, n - 1 );
}
for (int j = 0 ; j < n; j ) {
dfs(grid, 0 , j);
dfs(grid, m - 1 , j);
}
// 數(shù)一數(shù)剩下的陸地
int res = 0 ;
for (int i = 0 ; i < m; i ) {
for (int j = 0 ; j < n; j ) {
if (grid[i][j] == 1 ) {
res = 1 ;
}
}
}
return res;
}
// 和之前的實現(xiàn)類似
void dfs (int [][] grid, int i, int j) {
// ...
}
篇幅所限,具體代碼我就不寫了,我們繼續(xù)看其他的島嶼問題。
島嶼的最大面積
這是力扣第 695 題「島嶼的最大面積」,0表示海水,1表示陸地,現(xiàn)在不讓你計算島嶼的個數(shù)了,而是讓你計算最大的那個島嶼的面積,函數(shù)簽名如下:
int maxAreaOfIsland (int [][] grid)
比如題目給你輸入如下一個二維矩陣:
其中面積最大的是橘紅色的島嶼,算法返回它的面積 6。
這題的大體思路和之前完全一樣,只不過dfs函數(shù)淹沒島嶼的同時,還應該想辦法記錄這個島嶼的面積。
我們可以給dfs函數(shù)設(shè)置返回值,記錄每次淹沒的陸地的個數(shù),直接看解法吧:
int maxAreaOfIsland (int [][] grid) {
// 記錄島嶼的最大面積
int res = 0 ;
int m = grid.length, n = grid[0 ].length;
for (int i = 0 ; i < m; i ) {
for (int j = 0 ; j < n; j ) {
if (grid[i][j] == 1 ) {
// 淹沒島嶼,并更新最大島嶼面積
res = Math.max(res, dfs(grid, i, j));
}
}
}
return res;
}
// 淹沒與 (i, j) 相鄰的陸地,并返回淹沒的陸地面積
int dfs (int [][] grid, int i, int j) {
int m = grid.length, n = grid[0 ].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引邊界
return 0 ;
}
if (grid[i][j] == 0 ) {
// 已經(jīng)是海水了
return 0 ;
}
// 將 (i, j) 變成海水
grid[i][j] = 0 ;
return dfs(grid, i 1 , j)
dfs(grid, i, j 1 )
dfs(grid, i - 1 , j)
dfs(grid, i, j - 1 ) 1 ;
}
解法和之前相比差不多,我也不多說了,接下來的兩道島嶼問題是比較有技巧性的,我們重點來看一下。
子島嶼數(shù)量
如果說前面的題目都是模板題,那么力扣第 1905 題「統(tǒng)計子島嶼」可能得動動腦子了:
這道題的關(guān)鍵在于,如何快速判斷子島嶼?肯定可以借助 Union Find 并查集 算法來判斷,不過本文重點在 DFS 算法,就不展開并查集算法了。
什么情況下grid2中的一個島嶼B是grid1中的一個島嶼A的子島?
當島嶼B中所有陸地在島嶼A中也是陸地的時候,島嶼B是島嶼A的子島。
反過來說,如果島嶼B中存在一片陸地,在島嶼A的對應位置是海水,那么島嶼B就不是島嶼A的子島。
那么,我們只要遍歷grid2中的所有島嶼,把那些不可能是子島的島嶼排除掉,剩下的就是子島。
依據(jù)這個思路,可以直接寫出下面的代碼:
int countSubIslands (int [][] grid1, int [][] grid2) {
int m = grid1.length, n = grid1[0 ].length;
for (int i = 0 ; i < m; i ) {
for (int j = 0 ; j < n; j ) {
if (grid1[i][j] == 0
本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。