专栏：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算法文档 。
热门跟贴