面试官出车祸了，面试要取消了。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一网友发文称面试被取消了，原因是面试官在路上出车祸了。不知道是真出车祸，还是已经找到合适的人不打算招了。如果是不打算招了，说明HR和面试官的关系很不好，不想招完全可以找个其他借口。我之前也遇到过面试取消的情况，面试的当天HR给出的理由是面试官出差去了，后面再约，结果直到我重新找到工作入职，也没见她约。

不过也有可能是真的，不能瞎猜，不知道大家在面试中有没有遇到取消的情况。

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

来看下今天的算法题，这题是LeetCode的第827题：最大人工岛。

问题描述

来源：LeetCode第827题

难度：困难

给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，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 的时候，两个本来不相连的岛屿可能会相连，岛屿的面积就会增大，如下图所示。

所以在计算完岛屿面积之后，需要再遍历一次二维数组，如果是 0 ，就尝试把它变成 1 ，然后把它的上下左右 4 个方向有岛屿的连在一起计算面积。

为了连接的时候防止岛屿有重复，我们需要把每个岛屿编上号，如果号码是一样的，说明他们是同一个岛屿，不能连接，如下图所示，红色 0 的上下位置是同一个岛屿，不能相加。

JAVA：

// 每一个岛屿的区域标记为一个不同的数字 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;// 保存最大的岛屿         // 每一个岛屿的区域标记为一个不同的数字         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

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。