原題鏈接：島嶼的最大面積
題目描述
- 給定一個(gè)包含了一些
0和1的非空二維數(shù)組grid际度，一個(gè)島嶼是由四個(gè)方向（水平或垂直）的1（代表土地）構(gòu)成的組合。你可以假設(shè)二維矩陣的四個(gè)邊緣都被水包圍著涵妥。
- 找到給定的二維數(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。
其他注意事項(xiàng)
- 給定的矩陣
grid的長(zhǎng)度和寬度都不超過(guò)50锯厢。
思路描述
核心——DFS問(wèn)題皮官。
- 首先需要一個(gè)DFS方法，如果該點(diǎn)為
1实辑，則向四個(gè)方向遞歸捺氢；如果該點(diǎn)為0，則方法直接返回剪撬。該方法需要判斷邊界情況摄乒。
- 需要一個(gè)跟grid大小一樣的
boolean visited[][]數(shù)組來(lái)記錄該點(diǎn)是否已訪問(wèn)，防止重復(fù)訪問(wèn)残黑。
- 外層雙重循環(huán)遍歷所有的點(diǎn)馍佑，并比較每個(gè)點(diǎn)的DFS方法返回值，得到最大值梨水。
class Solution {
public int maxAreaOfIsland(int[][] grid) {
// 記錄該節(jié)點(diǎn)是否訪問(wèn)過(guò)
boolean[][] visited = new boolean[grid.length][grid[0].length];
// 記錄最大值
int max = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
max = Math.max(max, dfs(i, j, grid, visited));
}
}
return max;
}
private int dfs(int i, int j, int[][] grid, boolean[][] visited) {
// 邊界判斷
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
return 0;
}
// 重復(fù)訪問(wèn)判斷
if (visited[i][j]) {
return 0;
}
// 島嶼為0拭荤、1判斷
if (grid[i][j] == 0) {
return 0;
}
// 標(biāo)記該點(diǎn)為已訪問(wèn)
visited[i][j] = true;
// 四個(gè)方向遞歸
return 1 + dfs(i-1, j, grid, visited)
+ dfs(i+1, j, grid, visited)
+ dfs(i, j-1, grid, visited)
+ dfs(i, j+1, grid, visited);
}
}
優(yōu)化思路
- 如果原grid數(shù)組可以被修改，那么可以不使用輔助空間
visited[][]二維數(shù)組疫诽，直接修改原數(shù)組來(lái)做標(biāo)記
class Solution {
public int maxAreaOfIsland(int[][] grid) {
// 記錄最大值
int max = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
int temp = DFS(i, j, grid);
max = temp > max ? temp : max;
}
}
return max;
}
public int DFS(int i, int j, int[][] grid) {
// 邊界判斷
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
return 0;
}
// 島嶼為0穷劈、1判斷
if (grid[i][j] == 0) {
return 0;
}
// 標(biāo)記grid[i][j] = 0
grid[i][j] = 0;
// 四個(gè)方向遞歸
return 1 + DFS(i-1, j, grid)
+ DFS(i+1, j, grid)
+ DFS(i, j-1, grid)
+ DFS(i, j+1, grid);
}
}
一年又一年，字節(jié)跳動(dòng) Lark（飛書） 研發(fā)團(tuán)隊(duì)又雙叒叕開始招新生啦踊沸！
【內(nèi)推碼】：GTPUVBA
【招生對(duì)象】：20年9月后~21年8月前 畢業(yè)的同學(xué)
【報(bào)名時(shí)間】：6.16-7.16（提前批簡(jiǎn)歷投遞只有一個(gè)月抓住機(jī)會(huì)哦Ｐ铡）
【畫重點(diǎn)】：提前批和正式秋招不矛盾！面試成功逼龟，提前鎖定Offer评凝；若有失利，額外獲得一次面試機(jī)會(huì)腺律，正式秋招開啟后還可再次投遞奕短。
