力扣-图论-19【算法学习day.69】
前言###我做这类文章一个重要的目的照旧给正在学习的大家提供方向和记录学习过程（比方想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常具体，只会提供思绪和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！
习题
1.最大人工岛
题目链接:827. 最大人工岛 - 力扣（LeetCode）
题面:https://i-blog.csdnimg.cn/direct/ba4c792093a8436f8cdc347c8a56d670.png
分析:我最开始想用并查集做，将未改变的grid中的全部岛分别开来，然后遍历里面的0，看上下左右是否存在岛屿，如果存在求归并的巨细并更新最大值，遇到的一个麻烦就是grid是二维数组，怎么将x和y换算成一个不会重复的哈希值，所以这个方法我没行通，灵神也是这个思绪，不外是单独开一个集合来标记每个1属于哪个岛屿，多大，非常巧妙
灵神代码:
class Solution {
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int largestIsland(int[][] grid) {
int n = grid.length;
List<Integer> area = new ArrayList<>();
// DFS 每个岛，统计各个岛的面积，记录到 area 列表中
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid == 1) {
area.add(dfs(grid, i, j, area.size() + 2));
}
}
}
// 特判没有岛的情况
if (area.isEmpty()) {
return 1;
}
int ans = 0;
Set<Integer> s = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid != 0) {
continue;
}
s.clear();
int newArea = 1;
for (int[] dir : DIRS) {
int x = i + dir;
int y = j + dir;
if (0 <= x && x < n && 0 <= y && y < n && grid != 0 && s.add(grid)) {
newArea += area.get(grid - 2); // 累加面积
}
}
ans = Math.max(ans, newArea);
}
}
// 如果最后 ans 仍然为 0，说明所有格子都是 1，返回 n^2
return ans == 0 ? n * n : ans;
}
private int dfs(int[][] grid, int i, int j, int id) {
grid = id; // 记录 (i,j) 属于哪个岛
int size = 1;
for (int[] dir : DIRS) {
int x = i + dir;
int y = j + dir;
if (0 <= x && x < grid.length && 0 <= y && y < grid.length && grid == 1) {
size += dfs(grid, x, y, id);
}
}
return size;
}
}
后言
上面是力扣图论专题，下一篇是其他的习题，渴望有所资助，一同进步，共勉！
https://i-blog.csdnimg.cn/direct/ed1018eb3afd4765b6b0c2833cf5ad77.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]