專欄：50多種數(shù)據(jù)結構徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友發(fā)文稱面試被取消了，原因是面試官在路上出車禍了。不知道是真出車禍，還是已經(jīng)找到合適的人不打算招了。如果是不打算招了，說明HR和面試官的關系很不好，不想招完全可以找個其他借口。我之前也遇到過面試取消的情況，面試的當天HR給出的理由是面試官出差去了，后面再約，結果直到我重新找到工作入職，也沒見她約。

不過也有可能是真的，不能瞎猜，不知道大家在面試中有沒有遇到取消的情況。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第827題：最大人工島。

問題描述

來源：LeetCode第827題

難度：困難

給你一個大小為 n x n 二進制矩陣 grid 。最多只能將一格 0 變成 1 。返回執(zhí)行此操作后，grid 中最大的島嶼面積是多少？島嶼由一組上、下、左、右四個方向相連的 1 形成。

示例1：

輸入: grid = [[1, 0], [0, 1]] 輸出: 3 解釋: 將一格0變成1，最終連通兩個小島得到面積為 3 的島嶼。

示例2：

輸入: grid = [[1, 1], [1, 0]] 輸出: 4 解釋: 將一格0變成1，島嶼的面積擴大為 4。

• n == grid.length

• n == grid[i].length

• 1 <= n <= 500

• grid[i][j] 為 0 或 1

問題分析

這題說的是最多只能將一個 0 變成 1 ，然后求最大的島嶼面積，和我們之前講的 類似。

我們可以按照之前的方式先計算所有島嶼的面積，然后嘗試把 0 變成 1 ，計算最大面積。因為 0 變成的 1 的時候，兩個本來不相連的島嶼可能會相連，島嶼的面積就會增大，如下圖所示。

所以在計算完島嶼面積之后，需要再遍歷一次二維數(shù)組，如果是 0 ，就嘗試把它變成 1 ，然后把它的上下左右 4 個方向有島嶼的連在一起計算面積。

為了連接的時候防止島嶼有重復，我們需要把每個島嶼編上號，如果號碼是一樣的，說明他們是同一個島嶼，不能連接，如下圖所示，紅色 0 的上下位置是同一個島嶼，不能相加。

JAVA：

// 每一個島嶼的區(qū)域標記為一個不同的數(shù)字 public int largestIsland(int[][] grid) {     int length = grid.length;     Map
         
  mp =  new HashMap<>();      int ans =  0; // 保存最大的島嶼      int landNo =  2; // 島嶼編號從 2 開始      for ( int i =  0; i < length; i++) {          for ( int j =  0; j < length; j++) {              if (grid[i][j] ==  1) {                  int area = dfs(grid, i, j, length, landNo);                 mp.put(landNo++, area); // 保存到map中，島嶼編號也要累加                 ans = Math.max(ans, area);             }         }     }     Set  mySet =  new HashSet<>(); // 去掉重復的      for ( int i =  0; i < length; i++) {          for ( int j =  0; j < length; j++) {              // 如果遇到0，嘗試把它的上下左右連接起來，保存最大面積。              if (grid[i][j] ==  0) {                  int up = i >  0 ? grid[i -  1][j] :  0;                  int down = i < length -  1 ? grid[i +  1][j] :  0;                  int left = j >  0 ? grid[i][j -  1] :  0;                  int right = j < length -  1 ? grid[i][j +  1] :  0;                  // 上下左右在連接之前肯定是不能相連的，如果是相連的，只能取一個                 mySet.clear();                 mySet.addAll(Arrays.asList(up, down, left, right));                  int tmp =  0;                  for ( int s : mySet) {                      if (s !=  0)                         tmp += mp.get(s);                 }                 ans = Math.max(ans, tmp +  1);             }         }     }      return ans; } // 通過dfs遍歷當前位置的上下左右四個方向 private int dfs(int[][] grid, int i, int j, int length, int landNo) {      // 越界處理      if (i <  0 || i >= length || j <  0 || j >= length || grid[i][j] !=  1)          return  0;      int res =  1;     grid[i][j] = landNo; // 相連的標記為同一個島嶼     res += dfs(grid, i -  1, j, length, landNo); // 上     res += dfs(grid, i +  1, j, length, landNo); // 下     res += dfs(grid, i, j -  1, length, landNo); // 左     res += dfs(grid, i, j +  1, length, landNo); // 右      return res; }

C++：

public:     int largestIsland(vector

 > &grid) {         int length = grid.size();         unordered_map

  mp;         int ans = 0;// 保存最大的島嶼         // 每一個島嶼的區(qū)域標記為一個不同的數(shù)字         int landNo = 2;// 島嶼編號從 2 開始         for (int i = 0; i < length; i++) {             for (int j = 0; j < length; j++) {                 if (grid[i][j] == 1) {                     int area = dfs(grid, i, j, length, landNo);                     mp[landNo++] = area;// 保存到map中，島嶼編號也要累加                     ans = max(ans, area);                 }             }         }         unordered_set

  mySet;// 去掉重復的         for (int i = 0; i < length; i++) {             for (int j = 0; j < length; j++) {                 // 如果遇到0，嘗試把它的上下左右連接起來，保存最大面積。                 if (grid[i][j] == 0) {                     int up = i > 0 ? grid[i - 1][j] : 0;                     int down = i < length - 1 ? grid[i + 1][j] : 0;                     int left = j > 0 ? grid[i][j - 1] : 0;                     int right = j < length - 1 ? grid[i][j + 1] : 0;                     // 上下左右在連接之前肯定是不能相連的，如果是相連的，只能取一個                     mySet.clear();                     mySet.insert(up);                     mySet.insert(down);                     mySet.insert(left);                     mySet.insert(right);                     int tmp = 0;                     for (int s: mySet) {                         if (s != 0)                             tmp += mp[s];                     }                     ans = max(ans, tmp + 1);                 }             }         }         return ans;     }     // 通過dfs遍歷當前位置的上下左右四個方向     int dfs(vector

 > &grid, int i, int j, int length, int landNo) {         // 越界處理         if (i < 0 || i >= length || j < 0 || j >= length || grid[i][j] != 1)             return 0;         int res = 1;         grid[i][j] = landNo;// 相連的標記為同一個島嶼         res += dfs(grid, i - 1, j, length, landNo);// 上         res += dfs(grid, i + 1, j, length, landNo);// 下         res += dfs(grid, i, j - 1, length, landNo);// 左         res += dfs(grid, i, j + 1, length, landNo);// 右         return res;     }

Python：

def largestIsland(self, grid: List[List[int]]) -> int:     # 通過dfs遍歷當前位置的上下左右四個方向     def dfs(i, j, length, landNo):         # 越界處理         if i < 0 or i >= length or j < 0 or j >= length or grid[i][j] != 1:             return 0         res = 1         grid[i][j] = landNo  # 相連的標記為同一個島嶼         res += dfs(i - 1, j, length, landNo)  # 上         res += dfs(i + 1, j, length, landNo)  # 下         res += dfs(i, j - 1, length, landNo)  # 左         res += dfs(i, j + 1, length, landNo)  # 右         return res     length = len(grid)     mp = {}     ans = 0  # 保存最大的島嶼     landNo = 2  # 島嶼編號從 2 開始     for i in range(length):         for j in range(length):             if grid[i][j] == 1:                 area = dfs(i, j, length, landNo)                 mp[landNo] = area  # 保存到map中，島嶼編號也要累加                 ans = max(ans, area)                 landNo += 1     for i in range(length):         for j in range(length):             # 如果遇到0，嘗試把它的上下左右連接起來，保存最大面積。             if grid[i][j] == 0:                 up = grid[i - 1][j] if i > 0 else 0                 down = grid[i + 1][j] if i < length - 1 else 0                 left = grid[i][j - 1] if j > 0 else 0                 right = grid[i][j + 1] if j < length - 1 else 0                 # 上下左右在連接之前肯定是不能相連的，如果是相連的，只能取一個                 mySet = {up, down, left, right}  # 去掉重復的                 tmp = 0                 for s in mySet:                     if s != 0:                         tmp += mp[s]                 ans = max(ans, tmp + 1)     return ans

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結構和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。