当前位置:网站首页>Maximum artificial island [how to make all nodes of a connected component record the total number of nodes? + number the connected component]
Maximum artificial island [how to make all nodes of a connected component record the total number of nodes? + number the connected component]
2022-07-05 18:04:00 【REN_ Linsen】
dfs And connected components
Preface
How to find the total number of all nodes of connected components ?dfs+visited
How to record the total number of nodes of the connected component for all nodes of the connected component ? Change the variable to an array ( We use a heap address )
How to determine whether the nodes around a node are two different connected components ? Number the connected components or Union checking set findFather
One 、 The largest artificial island
Two 、DFS+ Search variant
package everyday.hard;
import java.util.HashSet;
import java.util.Set;
// The largest artificial island .
public class LargestIsland {
/* target: Only one grid can be removed from 0 Turn into 1, Look at the largest island area . intuitive :DFS Find island area , How to draw inferences from one instance ? Since only one 0 Turn into 1, Then from 0 The place of dfs, But the time complexity is very high !O(N * N * N * N) Then trade space for time , Pass each block in advance dfs Well done , From 1 The place of dfs, Each location records the total number of connected blocks . however , This will fail , because 0 The left and right connected blocks of may not be independent connected blocks , It may be the same connected block , It will lead to double calculation . therefore , You need to number connected component blocks , Different connected component blocks can be added together . */
public int largestIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int max = 1 << 31;
int[][][] f = new int[m][n][2];
// from 1 set out 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;
}
}
}
// from 0 set out 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;
// To duplicate the connected components
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;
}
// It is convenient to walk in four directions , Use matrix + The way of circulation .
static final int[][] gaps = new int[][]{
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
// How to make all nodes of a connected component be assigned to the total number of nodes .
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);
}
}
}
summary
1) The question is DFS+ Improved version of memory search , What you want to do is draw inferences from one instance , We must grasp the details firmly , For example, the visited needs are always marked , You can't leave it unmarked , You can't go back and remove the mark , This is not to find the maximum path value ; If the subscript is judged to be out of bounds , No i == 0 || i == n, yes i == -1 || i == n, This can be mistaken , I'm impressed .
2) Master these basic knowledge , According to the needs of the topic , To make corresponding use . For example, this topic can be a 0 become 1, Then it's better to start from 0 We're going to start traversing , Taking the maximum .
3) It's rather sad to do this today , Always feel that the idea is right ( But the idea is right , It's just that there's a hole that hasn't been found .), It took a lot of time to find the key problem .( The ability to find key problems is too weak , I think this is the core ability !). But don't be discouraged , Read the explanation of the question , Only to find that this is a hole deliberately given by the official , Need to break the comfort zone knowledge , Learn to draw inferences from one example , Grow step by step . So laugh if you want to lose , Read your thoughts out loud , If you can't figure it out, learn to solve the problem , This is a good time to break through yourself .
reference
边栏推荐
- 图像分类,看我就够啦!
- Leetcode notes: Weekly contest 300
- Zabbix
- VC编程入门浅谈「建议收藏」
- GFS distributed file system
- PMP认证需具备哪些条件啊?费用多少啊?
- Numerical calculation method chapter8 Numerical solutions of ordinary differential equations
- Data access - entityframework integration
- Sophon KG升级3.1:打破数据间壁垒,解放企业生产力
- Cmake tutorial Step3 (requirements for adding libraries)
猜你喜欢
Unicode processing in response of flash interface
吳恩達團隊2022機器學習課程,來啦
Find the first k small element select_ k
Thesis reading_ Medical NLP model_ EMBERT
Thesis reading_ Chinese NLP_ LTP
flask接口响应中的中文乱码(unicode)处理
Leetcode daily practice: rotating arrays
How awesome is the architecture of "12306"?
PMP认证需具备哪些条件啊?费用多少啊?
FCN: Fully Convolutional Networks for Semantic Segmentation
随机推荐
删除数组中的某几个元素
Zabbix
多线程(一) 进程与线程
How to modify MySQL fields as self growing fields
Cmake tutorial Step2 (add Library)
Elk log analysis system
Isprs2022 / Cloud Detection: Cloud Detection with Boundary nets Boundary Networks Based Cloud Detection
JVM第三话 -- JVM性能调优实战和高频面试题记录
Thesis reading_ Medical NLP model_ EMBERT
nano的CAN通信
通过SOCKS代理渗透整个内网
Data access - entityframework integration
记一次使用Windbg分析内存“泄漏”的案例
GFS distributed file system
ISPRS2022/雲檢測:Cloud detection with boundary nets基於邊界網的雲檢測
Redis基础
Xiaobai getting started with NAS - quick building private cloud tutorial series (I) [easy to understand]
Wu Enda team 2022 machine learning course, coming
华夏基金:基金行业数字化转型实践成果分享
LeetCode每日一题:合并两个有序数组