精品推薦：

《征服數(shù)據(jù)結(jié)構(gòu)》專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

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

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

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

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

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

輸入: grid = [[1, 0], [0, 1]]

輸出: 3

解釋: 將一格0變成1，最終連通兩個(gè)小島得到面積為 3 的島嶼。

輸入: grid = [[1, 1], [1, 0]]

輸出: 4

解釋: 將一格0變成1，島嶼的面積擴(kuò)大為 4。

// 每一個(gè)島嶼的區(qū)域標(biāo)記為一個(gè)不同的數(shù)字
public int largestIsland(int[][] grid) {
 int length = grid.length;
 Map<Integer, Integer> mp = new HashMap<>();
 int ans = 0;// 保存最大的島嶼
 int landNo = 2;// 島嶼編號(hào)從 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中，島嶼編號(hào)也要累加
 ans = Math.max(ans, area);
   }
  }
 }
 Set<Integer> mySet = new HashSet<>();// 去掉重復(fù)的
 for (int i = 0; i < length; i++) {
  for (int j = 0; j < length; j++) {
   // 如果遇到0，嘗試把它的上下左右連接起來(lái)，保存最大面積。
   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;
 // 上下左右在連接之前肯定是不能相連的，如果是相連的，只能取一個(gè)
 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;
}

// 通過(guò)dfs遍歷當(dāng)前位置的上下左右四個(gè)方向
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;// 相連的標(biāo)記為同一個(gè)島嶼
 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;
}

public:
 int largestIsland(vector<vector<int>> &grid) {
  int length = grid.size();
  unordered_map<int, int> mp;
  int ans = 0;// 保存最大的島嶼
  // 每一個(gè)島嶼的區(qū)域標(biāo)記為一個(gè)不同的數(shù)字
  int landNo = 2;// 島嶼編號(hào)從 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中，島嶼編號(hào)也要累加
  ans = max(ans, area);
 }
   }
  }
  unordered_set<int> mySet;// 去掉重復(fù)的
  for (int i = 0; i < length; i++) {
   for (int j = 0; j < length; j++) {
 // 如果遇到0，嘗試把它的上下左右連接起來(lái)，保存最大面積。
 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;
  // 上下左右在連接之前肯定是不能相連的，如果是相連的，只能取一個(gè)
  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;
 }

 // 通過(guò)dfs遍歷當(dāng)前位置的上下左右四個(gè)方向
 int dfs(vector<vector<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;// 相連的標(biāo)記為同一個(gè)島嶼
  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;
 }

def largestIsland(self, grid: List[List[int]]) -> int:
 # 通過(guò)dfs遍歷當(dāng)前位置的上下左右四個(gè)方向
 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  # 相連的標(biāo)記為同一個(gè)島嶼
  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  # 島嶼編號(hào)從 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中，島嶼編號(hào)也要累加
 ans = max(ans, area)
 landNo += 1

 for i in range(length):
  for j in range(length):
   # 如果遇到0，嘗試把它的上下左右連接起來(lái)，保存最大面積。
   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
 # 上下左右在連接之前肯定是不能相連的，如果是相連的，只能取一個(gè)
 mySet = {up, down, left, right}  # 去掉重復(fù)的
 tmp = 0
 for s in mySet:
  if s != 0:
   tmp += mp[s]
 ans = max(ans, tmp + 1)
 return ans