當(dāng)前位置:首頁 > 公眾號精選 > 程序員小灰
[導(dǎo)讀]讀完本文,可以去力扣解決如下題目:200.島嶼數(shù)量(中等)1254.統(tǒng)計(jì)封閉島嶼的數(shù)目(中等)1020.飛地的數(shù)量(中等)1905.統(tǒng)計(jì)子島嶼(中等)694.不同的島嶼數(shù)量(中等)島嶼問題是經(jīng)典的面試高頻題,雖然基本的島嶼問題并不難,但是島嶼問題有一些有意思的擴(kuò)展,比如求子島嶼數(shù)...

讀完本文,可以去力扣解決如下題目:200.島嶼數(shù)量(中等

1254.統(tǒng)計(jì)封閉島嶼的數(shù)目(中等

1020.飛地的數(shù)量(中等

1905.統(tǒng)計(jì)子島嶼(中等

694.不同的島嶼數(shù)量(中等

島嶼問題是經(jīng)典的面試高頻題,雖然基本的島嶼問題并不難,但是島嶼問題有一些有意思的擴(kuò)展,比如求子島嶼數(shù)量,求形狀不同的島嶼數(shù)量等等,本文就來把這些問題一網(wǎng)打盡。

島嶼系列問題的核心考點(diǎn)就是用 DFS/BFS 算法遍歷二維數(shù)組。

本文主要來講解如何用 DFS 算法來秒殺島嶼系列問題,不過用 BFS 算法的核心思路是完全一樣的,無非就是把 DFS 改寫成 BFS 而已。

那么如何在二維矩陣中使用 DFS 搜索呢?如果你把二維矩陣中的每一個(gè)位置看做一個(gè)節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)的上下左右四個(gè)位置就是相鄰節(jié)點(diǎn),那么整個(gè)矩陣就可以抽象成一幅網(wǎng)狀的「圖」結(jié)構(gòu)。

根據(jù)學(xué)習(xí)數(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;
????}
????//?前序:進(jìn)入節(jié)點(diǎn)?(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é)點(diǎn)?(i, j)
????// visited[i][j]?=?true;
}
因?yàn)槎S矩陣本質(zhì)上是一幅「圖」,所以遍歷的過程中需要一個(gè)visited布爾數(shù)組防止走回頭路,如果你能理解上面這段代碼,那么搞定所有島嶼問題都很簡單。

這里額外說一個(gè)處理二維數(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;
????}

????//?進(jìn)入節(jié)點(diǎn)?(i,?j)
????visited[i][j]?=?true;
????//?遞歸遍歷上下左右的節(jié)點(diǎn)
????for?(int[]?d?:?dirs)?{
????????int?next_i?=?i? ?d[0];
????????int?next_j?=?j? ?d[1];
????????dfs(grid,?next_i,?next_j);
????}
????//?離開節(jié)點(diǎn)?(i,?j)
????// visited[i][j]?=?true;
}
這種寫法無非就是用 for 循環(huán)處理上下左右的遍歷罷了,你可以按照個(gè)人喜好選擇寫法。

島嶼數(shù)量

這是力扣第 200 題「島嶼數(shù)量」,最簡單也是最經(jīng)典的一道島嶼問題,題目會輸入一個(gè)二維數(shù)組grid,其中只包含0或者1,0代表海水,1代表陸地,且假設(shè)該矩陣四周都是被海水包圍著的。

我們說連成片的陸地形成島嶼,那么請你寫一個(gè)算法,計(jì)算這個(gè)矩陣grid中島嶼的個(gè)數(shù),函數(shù)簽名如下:

int?numIslands(char[][]?grid);
比如說題目給你輸入下面這個(gè)grid有四片島嶼,算法應(yīng)該返回 4:

思路很簡單,關(guān)鍵在于如何尋找并標(biāo)記「島嶼」,這就要 DFS 算法發(fā)揮作用了,我們直接看解法代碼:

//?主函數(shù),計(jì)算島嶼數(shù)量
int?numIslands(char[][]?grid)?{
????int?res?=?0;
????int?m?=?grid.length,?n?=?grid[0].length;
????//?遍歷?grid
????for?(int?i?=?0;?i?????????for?(int?j?=?0;?j?????????????if?(grid[i][j]?==?'1')?{
????????????????//?每發(fā)現(xiàn)一個(gè)島嶼,島嶼數(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 算法把島嶼「淹了」呢?主要是為了省事,避免維護(hù)visited數(shù)組。

因?yàn)?code style="margin-right: 2px;margin-left: 2px;padding: 2px 4px;font-size: inherit;line-height: inherit;border-radius: 4px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">dfs函數(shù)遍歷到值為0的位置會直接返回,所以只要把經(jīng)過的位置都設(shè)置為0,就可以起到不走回頭路的作用。

PS:這類 DFS 算法還有個(gè)別名叫做 FloodFill 算法,現(xiàn)在有沒有覺得 FloodFill 這個(gè)名字還挺貼切的~

這個(gè)最最基本的島嶼問題就說到這,我們來看看后面的題目有什么花樣。

封閉島嶼的數(shù)量

上一題說二維矩陣四周可以認(rèn)為也是被海水包圍的,所以靠邊的陸地也算作島嶼。

力扣第 1254 題「統(tǒng)計(jì)封閉島嶼的數(shù)目」和上一題有兩點(diǎn)不同:

1、用0表示陸地,用1表示海水。

2、讓你計(jì)算「封閉島嶼」的數(shù)目。所謂「封閉島嶼」就是上下左右全部被1包圍的0,也就是說靠邊的陸地不算作「封閉島嶼」。

函數(shù)簽名如下:

int?closedIsland(int[][]?grid)
比如題目給你輸入如下這個(gè)二維矩陣:

算法返回 2,只有圖中灰色部分的0是四周全都被海水包圍著的「封閉島嶼」。

那么如何判斷「封閉島嶼」呢?其實(shí)很簡單,把上一題中那些靠邊的島嶼排除掉,剩下的不就是「封閉島嶼」了嗎?

有了這個(gè)思路,就可以直接看代碼了,注意這題規(guī)定0表示陸地,用1表示海水:

//?主函數(shù):計(jì)算封閉島嶼的數(shù)量
int?closedIsland(int[][]?grid)?{
????int?m?=?grid.length,?n?=?grid[0].length;
????for?(int?j?=?0;?j?????????//?把靠上邊的島嶼淹掉
????????dfs(grid,?0,?j);
????????//?把靠下邊的島嶼淹掉
????????dfs(grid,?m?-?1,?j);
????}
????for?(int?i?=?0;?i?????????//?把靠左邊的島嶼淹掉
????????dfs(grid,?i,?0);
????????//?把靠右邊的島嶼淹掉
????????dfs(grid,?i,?n?-?1);
????}
????//?遍歷?grid,剩下的島嶼都是封閉島嶼
????int?res?=?0;
????for?(int?i?=?0;?i?????????for?(int?j?=?0;?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ù)剩下的陸地?cái)?shù)量就行了,注意第 1020 題中1代表陸地,0代表海水:

int?numEnclaves(int[][]?grid)?{
????int?m?=?grid.length,?n?=?grid[0].length;
????//?淹掉靠邊的陸地
????for?(int?i?=?0;?i?????????dfs(grid,?i,?0);
????????dfs(grid,?i,?n?-?1);
????}
????for?(int?j?=?0;?j?????????dfs(grid,?0,?j);
????????dfs(grid,?m?-?1,?j);
????}

????//?數(shù)一數(shù)剩下的陸地
????int?res?=?0;
????for?(int?i?=?0;?i?????????for?(int?j?=?0;?j?????????????if?(grid[i][j]?==?1)?{
????????????????res? =?1;
????????????}
????????}
????}

????return?res;
}

//?和之前的實(shí)現(xiàn)類似
void?dfs(int[][]?grid,?int?i,?int?j)?{
????//?...
}
篇幅所限,具體代碼我就不寫了,我們繼續(xù)看其他的島嶼問題。

島嶼的最大面積

這是力扣第 695 題「島嶼的最大面積」,0表示海水,1表示陸地,現(xiàn)在不讓你計(jì)算島嶼的個(gè)數(shù)了,而是讓你計(jì)算最大的那個(gè)島嶼的面積,函數(shù)簽名如下:

int?maxAreaOfIsland(int[][]?grid)
比如題目給你輸入如下一個(gè)二維矩陣:

其中面積最大的是橘紅色的島嶼,算法返回它的面積 6。

這題的大體思路和之前完全一樣,只不過dfs函數(shù)淹沒島嶼的同時(shí),還應(yīng)該想辦法記錄這個(gè)島嶼的面積。

我們可以給dfs函數(shù)設(shè)置返回值,記錄每次淹沒的陸地的個(gè)數(shù),直接看解法吧:

int?maxAreaOfIsland(int[][]?grid)?{
????//?記錄島嶼的最大面積
????int?res?=?0;
????int?m?=?grid.length,?n?=?grid[0].length;
????for?(int?i?=?0;?i?????????for?(int?j?=?0;?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;
}
解法和之前相比差不多,我也不多說了,接下來的兩道島嶼問題是比較有技巧性的,我們重點(diǎn)來看一下。

子島嶼數(shù)量

如果說前面的題目都是模板題,那么力扣第 1905 題「統(tǒng)計(jì)子島嶼」可能得動(dòng)動(dòng)腦子了:

這道題的關(guān)鍵在于,如何快速判斷子島嶼?肯定可以借助 Union Find 并查集 算法來判斷,不過本文重點(diǎn)在 DFS 算法,就不展開并查集算法了。

什么情況下grid2中的一個(gè)島嶼Bgrid1中的一個(gè)島嶼A的子島?

當(dāng)島嶼B中所有陸地在島嶼A中也是陸地的時(shí)候,島嶼B是島嶼A的子島。

反過來說,如果島嶼B中存在一片陸地,在島嶼A的對應(yīng)位置是海水,那么島嶼B就不是島嶼A的子島。

那么,我們只要遍歷grid2中的所有島嶼,把那些不可能是子島的島嶼排除掉,剩下的就是子島。

依據(jù)這個(gè)思路,可以直接寫出下面的代碼:

int?countSubIslands(int[][]?grid1,?int[][]?grid2)?{
????int?m?=?grid1.length,?n?=?grid1[0].length;
????for?(int?i?=?0;?i?????????for?(int?j?=?0;?j?????????????if?(grid1[i][j]?==?0?
本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時(shí)聯(lián)系本站刪除。
關(guān)閉