当前位置:网站首页>最大人工岛[如何让一个连通分量的所有节点都记录总节点数?+给连通分量编号]
最大人工岛[如何让一个连通分量的所有节点都记录总节点数?+给连通分量编号]
2022-07-05 17:49:00 【REN_林森】
dfs与连通分量
前言
如何求连通分量总的所有节点数?dfs+visited
如何给连通分量的所有节点都能记录该连通分量的节点总数?将变量改为数组(大家用一个堆地址)
如何确定一个节点周围的节点是否为两个不同的连通分量?给连通分量编号 or 并查集findFather
一、最大人工岛
二、DFS+记搜变体
package everyday.hard;
import java.util.HashSet;
import java.util.Set;
// 最大人工岛。
public class LargestIsland {
/* target:只能将一个格子从0变为1,看最大岛屿面积。 直观:DFS求岛屿面积, 如何举一反三?既然只能让一个0变为1,那就从0的地方dfs,但是时间复杂度非常高!O(N * N * N * N) 那用空间换时间,把每个块的提前通过dfs算好,即从1的地方dfs,每个位置都记录这个连通块的总数量。 但是,这会失败,因为0的左右连通块可能不是独立的连通块,可能就是同一个连通块,则会导致重复计算。 所以,需要给连通分量块编号,不同的连通分量块才能加在一起。 */
public int largestIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int max = 1 << 31;
int[][][] f = new int[m][n][2];
// 从1出发dfs
int idx = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
int[] total = new int[]{
0, idx};
dfs(grid, i, j, f, total);
max = Math.max(max, total[0]);
++idx;
}
}
}
// 从0出发dfs。
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 0) {
int total = 1;
// 去重复的连通分量
Set<Integer> bool = new HashSet<>();
for (int[] gap : gaps) {
int ni = i + gap[0], nj = j + gap[1];
if (ni == -1 || -1 == nj || nj == grid[0].length || grid.length == ni || grid[ni][nj] == 0)
continue;
if (!bool.contains(f[i][j][1])) {
total += f[i][j][0];
bool.add(f[i][j][1]);
}
}
max = Math.max(max, total);
}
}
}
return max;
}
// 方便走四个方向,采用矩阵+循环的方式。
static final int[][] gaps = new int[][]{
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
// 如何让一个连通分量的所有节点处都能赋值到总节点数。
private void dfs(int[][] grid, int i, int j, int[][][] f, int[] total) {
if (i == -1 || -1 == j || j == grid[0].length || grid.length == i || grid[i][j] <= 0) return;
total[0]++;
f[i][j] = total;
grid[i][j] = -1;
for (int[] gap : gaps) {
int ni = i + gap[0], nj = j + gap[1];
dfs(grid, ni, nj, f, total);
}
}
}
总结
1)这个题是DFS+记忆搜索的改进版本,想做的举一反三,就必须牢牢掌握其细节,如访问过的需要一直标记着,不能不标记,也不能回溯把标记去掉,这不是求最大路径值;如判定下标越界,不是i == 0 || i == n,是i == -1 || i == n,这都能搞错,服了。
2)掌握了这些基础知识,根据题目需求,来做相应的利用。比如本题可把一个0变成1,那不如就从0的地方开始遍历,取最大值。
3)今天做到这个比较丧,一直感觉思路是对的(不过思路是对的,只是有坑没发现。),花了很多时间才发现关键问题所在。(发现关键问题的能力太弱了,我觉得这是核心能力!)。但是不要气馁,看了题解,才发现这是官方故意给的坑,需要打破舒适区知识,学会举一反三,循序渐进的成长。所以想丧就要笑,大声把思路读出来,想不通就去学题解,这是突破自己的好时机。
参考文献
[1] LeetCode 最大人工岛
边栏推荐
- ITK Example
- Delete some elements in the array
- Cmake tutorial Step3 (requirements for adding libraries)
- Leetcode daily question: the first unique character in the string
- mybash
- PMP认证需具备哪些条件啊?费用多少啊?
- Redis Foundation
- Humi analysis: the integrated application of industrial Internet identity analysis and enterprise information system
- [JMeter] advanced writing method of JMeter script: all variables, parameters (parameters can be configured by Jenkins), functions, etc. in the interface automation script realize the complete business
- Sophon KG升级3.1:打破数据间壁垒,解放企业生产力
猜你喜欢
Ten capabilities that cyber threat analysts should have
7 pratiques devops pour améliorer la performance des applications
LeetCode每日一题:合并两个有序数组
LeetCode 练习——206. 反转链表
Redis基础
Tencent music launched its new product "quyimai", which provides music commercial copyright authorization
Mongodb (quick start) (I)
MATLAB查阅
提高应用程序性能的7个DevOps实践
基于YOLOv3的口罩佩戴检测
随机推荐
数据访问 - EntityFramework集成
Seven Devops practices to improve application performance
较文心损失一点点性能提升很多
提高应用程序性能的7个DevOps实践
rsync
访问数据库使用redis作为mysql的缓存(redis和mysql结合)
VBA drives SAP GUI to realize office automation (II): judge whether elements exist
Knowledge points of MySQL (6)
ISPRS2022/雲檢測:Cloud detection with boundary nets基於邊界網的雲檢測
QT console printout
Redis基础
rsync
网络威胁分析师应该具备的十种能力
Tkinter window preload
Matlab reference
论文阅读_中文NLP_LTP
Leetcode daily question: the first unique character in the string
Career advancement Guide: recommended books for people in big factories
How to modify MySQL fields as self growing fields
Oracle recovery tools -- Oracle database recovery tool