|
精品推薦：
《征服數(shù)據(jù)結(jié)構(gòu)》專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服 《經(jīng)典圖論算法》專欄：50多種經(jīng)典圖論算法全部掌握 隨著2025年春節(jié)的日益臨近，各大互聯(lián)網(wǎng)公司的春節(jié)假期安排和年終獎(jiǎng)發(fā)放成為了廣大員工和網(wǎng)友們熱議的話題。 12月23日，京東發(fā)布了2024年年終獎(jiǎng)發(fā)放計(jì)劃，這是京東要實(shí)現(xiàn)從16薪邁向20薪的第一年。實(shí)現(xiàn)17薪的部門內(nèi)年度績(jī)效A+的員工將實(shí)現(xiàn)20薪，采銷崗平均23薪，差不多相當(dāng)于干一年發(fā)兩年的工資，這年終獎(jiǎng)確實(shí)挺誘人。 --------------下面是今天的算法題-------------- 來看下今天的算法題，這題是LeetCode的第695題：島嶼的最大面積。 給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 grid 。島嶼是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個(gè) 1 必須在水平或者豎直的四個(gè)方向上相鄰。你可以假設(shè) grid 的四個(gè)邊緣都被 0（代表水）包圍著。 島嶼的面積是島上值為 1 的單元格的數(shù)目。計(jì)算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。 輸入：grid = [[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 解釋：答案不應(yīng)該是 11 ，因?yàn)閸u嶼只能包含水平或垂直這四個(gè)方向上的 1 。
m == grid.length n == grid[i].length 1 <= m, n <= 50 grid[i][j] 為 0 或 1
這題讓計(jì)算島嶼的最大面積，島嶼的面積是通過上下左右相連接的 1 的個(gè)數(shù)。這題有多種解決方式，BFS，DFS和并查集都可以解決，之前我們講過這道題，當(dāng)時(shí)使用的是 BFS-島嶼的最大面積，這里我們使用 DFS 再來解這道題。在矩陣中每個(gè)位置最多只有上下左右四個(gè)和它相連，我們遍歷矩陣的每一個(gè)位置，如果當(dāng)前位置是 1 ，表示它是島嶼，然后開始計(jì)算島嶼的面積。就是以當(dāng)前位置為起始點(diǎn)沿著它的上下左右四個(gè)方向查找，如果遇到 1 ，說明它們是同一個(gè)島嶼，累加面積，然后再把它變成 0 ，表示該位置已經(jīng)計(jì)算過了，防止重復(fù)計(jì)算，最后只需要返回最大面積即可。這里還要注意遍歷的時(shí)候不能越界，只能訪問矩陣內(nèi)的位置。public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;// 矩陣的寬和高
int ans = 0;// 記錄最大面積
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) // 當(dāng)前位置如果是 1 ，開始計(jì)算
ans = Math.max(ans, dfs(grid, i, j, m, n));
return ans;
}
public int dfs(int[][] grid, int i, int j, int m, int n) {
// 邊界條件的判斷，不能越界
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
// 當(dāng)前位置如果是1，為了防止重復(fù)計(jì)算就把他置為0，然后再?gòu)乃纳舷伦笥宜膫€(gè)方向開始查找
grid[i][j] = 0;
return 1 + dfs(grid, i + 1, j, m, n) + dfs(grid, i - 1, j, m, n)
+ dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n);
}
return 0;
}
public:
int maxAreaOfIsland(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();// 矩陣的寬和高
int ans = 0;// 記錄最大面積
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) // 當(dāng)前位置如果是 1 ，開始計(jì)算
ans = max(ans, dfs(grid, i, j, m, n));
return ans;
}
int dfs(vector<vector<int>> &grid, int i, int j, int m, int n) {
// 邊界條件的判斷，不能越界
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
// 當(dāng)前位置如果是1，為了防止重復(fù)計(jì)算就把他置為0，然后再?gòu)乃纳舷伦笥宜膫€(gè)方向開始查找
grid[i][j] = 0;
return 1 + dfs(grid, i + 1, j, m, n) + dfs(grid, i - 1, j, m, n)
+ dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n);
}
return 0;
}
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(i, j):
# 邊界條件的判斷，不能越界
if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:
# 當(dāng)前位置如果是1，為了防止重復(fù)計(jì)算就把他置為0，然后再?gòu)乃纳舷伦笥宜膫€(gè)方向開始查找
grid[i][j] = 0
return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
return 0
m, n = len(grid), len(grid[0]) # 矩陣的寬和高
ans = 0 # 記錄最大面積
for i in range(m):
for j in range(n):
if grid[i][j] == 1: # 當(dāng)前位置如果是 1 ，開始計(jì)算
ans = max(ans, dfs(i, j))
return ans
博哥，真名：王一博，畢業(yè)十多年，《算法秘籍》作者，專注于數(shù)據(jù)結(jié)構(gòu)和算法的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以下載我整理的1000多頁的PDF算法文檔。
|
