这个题涉及到hash表与二分查找，发现之前2529.正整数和负整数的最大计数里面寻找上界写错了。
有时间了再整理一下吧。
作者： admin
2739.总行驶距离
目标
卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。
该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。
示例 1：
输入：mainTank = 5, additionalTank = 10
输出：60
解释：
在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。
在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。
总行驶距离为 60km 。示例 2：
输入：mainTank = 1, additionalTank = 2
输出：10
解释：
在用掉 1 升燃料后，主油箱变为空。
总行驶距离为 10km 。说明：
- 1 <= mainTank, additionalTank <= 100
思路
这里面的关键点在于第一次消耗完5升燃料之后会触发副油箱注入，后面消耗的5升燃料中包含有副油箱注入的1升。即第一次消耗完成后主油箱每消耗4升就会触发燃料注入。
例如主油箱有9L，副油箱有1L，那么总共可以消耗10L燃料。
注入燃料的总次数等于 1 + (mainTank -5)/4 = (mainTank - 1)/4。
代码
/**
* @date 2024-04-25 0:11
*/
public class DistanceTraveled2739 {
public int distanceTraveled_v1(int mainTank, int additionalTank) {
return 10 * (mainTank + Math.min((mainTank - 1) / 4, additionalTank));
}
public int distanceTraveled(int mainTank, int additionalTank) {
int res = 0;
while (mainTank >= 5) {
res += 5;
mainTank -= 5;
if (additionalTank > 0) {
additionalTank--;
mainTank++;
}
}
res += mainTank;
return res * 10;
}
}性能
2385.感染二叉树需要的总时间
目标
给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。
每分钟，如果节点满足以下全部条件，就会被感染：
- 节点此前还没有感染。
- 节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。
示例 1：
输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：
- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9 和 2
感染整棵树需要 4 分钟，所以返回 4 。示例 2：
输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。说明：
- 树中节点的数目在范围 [1, 10^5] 内
- 1 <= Node.val <= 10^5
- 每个节点的值 互不相同
- 树中必定存在值为 start 的节点
思路
从树中任意节点开始，每过一分钟感染会向周围扩散，问感染整棵树需要多久。
首先我们要找到感染开始的节点。从这个节点出发，向左右子树点以及父节点扩散。可以将树转换为以感染节点为起点的有向无环连通图，这样问题被转换为求起点到图中任意节点的最长路径。
如果不想建图可以考虑扩散的具体路径，刚开始很难把各种情况都考虑到。我们需要计算以开始节点为根的子树高度 h(start)，并依次比较开始节点到祖先节点路径长度加上祖先另一子树高度的最大值，即max(d(start) - d(ancestor) + h(anotherAncestorSubtree))，再取二者的最大值即可。特别需要注意的是，不能使用子树高度之差来计算祖先与开始节点的路径长度。例如，E是开始节点，E到B的路径长度为d(E) - d(B) = 2 - 1 = 1，而如果使用子树高度相减的话就得到了h(B) - h(E) = 3 - 0 = 3。
A
/ \
B C
/ \
D E
|
F
|
G在具体实现的时候如何判断祖先节点的哪个子树包含开始节点困扰了我半天。刚开始我选择了一个标志位，分别在左右子树递归结束的时候检测该标志，发现找到之后立即重置该标志，这样父节点就知道了是左子树还是右子树包含开始节点。但问题是再向上返回的时候就无法判断了。
可以考虑返回二维数组，也有网友的题解使用返回值的符号来标识是否找到开始节点。
代码
/**
* @date 2024-04-24 8:56
*/
public class AmountOfTime2385 {
int startToParentToLeaf = 0;
int startToLeaf = 0;
int cnt = 0;
public int amountOfTime(TreeNode root, int start) {
dfs(root, start);
return Math.max(startToLeaf, startToParentToLeaf);
}
/**
* 返回子树深度
*/
public int[] dfs(TreeNode root, int start) {
if (root == null) {
return new int[]{0, 0};
}
int[] l = dfs(root.left, start);
int[] r = dfs(root.right, start);
boolean lfind = l[1] == 1;
boolean rfind = r[1] == 1;
int max = Math.max(r[0], l[0]);
if (lfind || rfind) {
startToParentToLeaf = Math.max(startToParentToLeaf, l[0] + r[0]);
// 这里的返回值不是max，而是祖先节点到开始节点的路径长度
return new int[]{(lfind ? l[0] : r[0]) + 1, 1};
}
if (root.val == start) {
startToLeaf = max;
// 这里直接返回1，不加max
// 视为将开始节点的左右子树删掉，后面回溯时直接相加左右子树高度即可
return new int[]{1, 1};
}
return new int[]{max + 1, 0};
}
/**
* 返回深度
*/
public int[] dfs_v1(TreeNode root, int start, int depth) {
if (root == null) {
return new int[]{depth - 1, 0};
}
int[] l = dfs_v1(root.left, start, depth + 1);
int[] r = dfs_v1(root.right, start, depth + 1);
boolean lfind = l[1] == 1;
boolean rfind = r[1] == 1;
int max = Math.max(r[0], l[0]);
if (lfind) {
cnt++;
startToParentToLeaf = Math.max(r[0] - depth + cnt, startToParentToLeaf);
}
if (rfind) {
cnt++;
startToParentToLeaf = Math.max(l[0] - depth + cnt, startToParentToLeaf);
}
if (root.val == start) {
startToLeaf = max - depth;
return new int[]{max, 1};
}
return new int[]{max, l[1] + r[1]};
}
}
性能
1052.爱生气的书店老板
目标
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
示例 1：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.示例 2：
输入：customers = [1], grumpy = [0], minutes = 1
输出：1说明：
- n == customers.length == grumpy.length
- 1 <= minutes <= n <= 2 * 10^4
- 0 <= customers[i] <= 1000
- grumpy[i] == 0 or 1
思路
这道题要我们求满意顾客的最大值，老板会在指定的分钟生气，生气时，当前进入的顾客就会不满意，老板可以有一次忍耐的机会在一段时间内不生气。
刚开始想复杂了，以为顾客不是马上离开，而是在i分钟后离开。其实是第i分钟结束的时候就离开了。
因此，我们只需要计算老板忍耐的时间内，原本生气影响的顾客最大值，然后再加上不生气时的顾客总数即可。
这就是一个滑动窗口问题，窗口大小为忍耐时间，记录窗口内的不满意顾客的最大值。
这里面可以优化的点是使用乘法来代替条件判断，这样可以避免分支预测失败导致额外的性能损失。
代码
/**
* @date 2024-04-23 8:40
*/
public class MaxSatisfied1052 {
public int maxSatisfied_v1(int[] customers, int[] grumpy, int minutes) {
int n = customers.length;
int total = 0;
for (int i = 0; i < n; i++) {
total += customers[i] * (1 - grumpy[i]);
}
int unsatisfiedInWindow = 0;
for (int i = 0; i < minutes; i++) {
unsatisfiedInWindow += customers[i] * grumpy[i];
}
int max = unsatisfiedInWindow;
for (int i = minutes; i < n; i++) {
unsatisfiedInWindow = unsatisfiedInWindow
- customers[i - minutes] * grumpy[i - minutes]
+ customers[i] * grumpy[i];
max = Math.max(max, unsatisfiedInWindow);
}
return total + max;
}
}
性能
377.组合总和 Ⅳ
目标
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。请注意，顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)示例 2：
输入：nums = [9], target = 3
输出：0说明：
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- nums 中的所有元素 互不相同
- 1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
思路
这个题要求满足条件的排列数，从给定数组中选择任意数字，同一数字可以重复选择，使所选序列的和等于target。
首先初始化给定数组的dp，然后遍历0~target，计算dp。
代码
/**
* @date 2024-04-22 8:31
*/
public class CombinationSum377 {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] dp = new int[target + 1];
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= target) {
dp[nums[i]] = 1;
}
}
for (int i = 0; i <= target; i++) {
for (int num : nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
性能
216.组合总和 III
目标
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。说明:
- 2 <= k <= 9
- 1 <= n <= 60
思路
从1~9中选k个，使它们的和是n。暴力求解需要 C9k 次遍历，可以使用回溯算法成批地考察具有特定前缀的所有候选解，一旦发现与目标解不合，需要撤销当前选择返回上一层进行下一个可能的尝试。dfs只是回溯算法的一环。关于回溯算法具体可参考《数据结构与算法分析》第314页。
代码
/**
* @date 2024-04-21 20:44
*/
public class CombinationSum216 {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= 9; i++) {
dfs(k - 1, i, n, q, res);
}
return res;
}
public void dfs(int k, int root, int target, Deque<Integer> q, List<List<Integer>> res) {
if (k < 0 || target < 0) {
return;
}
if (target == root && k == 0) {
q.offer(root);
res.add(new ArrayList<>(q));
q.pollLast();
return;
}
q.offer(root);
for (int i = root + 1; i <= 9; i++) {
dfs(k - 1, i, target - root, q, res);
}
q.pollLast();
}
}
性能
39.组合总和
目标
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
输入: candidates = [2], target = 1
输出: []提示：
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素 互不相同
- 1 <= target <= 40
思路
一看到这道题就想到要用动态规划，但是昨天看了回溯算法的视频，所以就试图使用dfs去写。
先从target开始，循环减去可选数字，然后递归。想法是好的，但是这种集合嵌套集合的操作一会就把我搞晕了，向下传递什么，返回什么？有机会再想想吧。
还是用动态规划吧，难点在于去重。刚开始甚至写了hash函数，但是它不能处理2, 5（2 3） 与 4（2 2）, 3的情况，dp[2] + dp[5] 与 dp[4] + dp[3] 得到的组合是相同的 [2, 2, 3]。
这让我想到了518.零钱兑换II，这两道题本质是一样的。那个只让返回组合数，这个需要返回具体的组合。
去重的精髓就在于不能提前初始化dp，只能在第一次访问到候选值的时候初始化。
代码
/**
* @date 2024-04-20 10:20
*/
public class CombinationSum39 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>>[] dp = new List[target + 1];
for (int i = 0; i <= target; i++) {
dp[i] = new ArrayList<>();
}
for (int candidate : candidates) {
if (candidate <= target) {
List<Integer> list = new ArrayList<>();
list.add(candidate);
dp[candidate].add(list);
}
for (int i = candidate; i <= target; i++) {
for (List<Integer> lj : dp[i - candidate]) {
List<Integer> tmp = new ArrayList<>();
tmp.add(candidate);
tmp.addAll(lj);
dp[i].add(tmp);
}
}
}
return dp[target];
}
}
性能
1883. 准时抵达会议现场的最小跳过休息次数
一周这么多道困难题，真的消化不了啊。
2007.从双倍数组中还原原数组
目标
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
示例 1：
输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。示例 2：
输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。示例 3：
输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。说明：
- 1 <= changed.length <= 10^5
- 0 <= changed[i] <= 10^5
思路
所谓双倍数组指的是由原数组以及其每个元素乘以2之后的元素合并在一起的数组。现在想要从双倍数组还原为原数组，如果不是合法的双倍数组则返回空数组。
首先，如果元素个数为奇数肯定不是双倍数组。注意到数组中的元素如果是奇数那么一定属于原数组。由于返回数组的顺序任意，那么先排序会更好处理。
接着就想到将奇数与偶数分开，然后看奇数*2是否有相应的偶数对应，或者可以将偶数元素/2看是否有奇数对应（不过这样就得处理0的情况，因为0只能与它自己匹配）。匹配完成后可能还剩下原数组中的偶数元素与其对应的双倍元素。
该如何处理呢？看了具体的例子很容易有一些想当然的想法，比如剩余[2,2,4,4]很容易将其平分为两部分，然后同时比较这两部分相应的位置是否满足二倍关系。这种假设是没有根据的，也是不对的，比如剩余[2、2、4、4、4、6、8、12]也是合法的。那我们该怎么比较呢？
这时突然有一个想法出现在大脑中，可以先将当前元素存到队列中，如果后面的元素不是其二倍就添加到队列中，如果是则将队列的第一个元素取出，这样遍历完之后看队列中是否还有数据即可。我们之所以可以这么做是因为前面排过序了，队首元素的二倍元素一定会最先出现。如果不排序的话，比如说[2,1]，2先加入队列，后加入的1就无法匹配了。再比如[4,8,2,16]，4与8匹配了，剩下的就匹配不了了。
有了这个想法之后，前面区分奇数、偶数，对0做特殊处理就都没有必要了。
网友还介绍了一种消消乐的方法，可以不排序。这个需要先统计各元素出现的次数，然后如果x % 2 == 0 && cnt.containsKey(x / 2)则跳过，即如果 x/2 在 cnt 中，则跳过，直到找到开始的那个x，然后一次性处理之前被跳过的2x、4x、6x...。这里其实也利用了顺序，只不过没有排序而是先找到不能再分的那个初始节点再向后倍增。
还有的使用大数组保存了 0~max 元素出现次数的数组cnt，然后遍历cnt，如果cnt[i]>0 而 2*i>max || cnt[2i]==0 直接返回空数组，否则cnt[2i]--。这个方法也不用排序，是因为统计个数时变相地将数组元素映射为下标，遍历cnt数组是从小到大有序的。
代码
/**
* @date 2024-04-18 8:48
*/
public class FindOriginalArray2007 {
public int[] findOriginalArray(int[] changed) {
int n = changed.length;
if (n % 2 == 1) {
return new int[0];
}
Arrays.sort(changed);
int originLength = n / 2;
int[] res = new int[originLength];
Deque<Integer> collect = new ArrayDeque<>();
int i = 0;
for (int j = 0; j < changed.length; j++) {
if (collect.size() == 0 || changed[j] % 2 == 1 || !collect.peek().equals(changed[j] / 2)) {
collect.add(changed[j]);
} else {
res[i++] = collect.poll();
}
}
if (collect.size() > 0) {
return new int[0];
}
return res;
}
}
性能
928.尽量减少恶意软件的传播II
目标
给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0示例 2：
输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1示例 3：
输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1说明：
- n == graph.length
- n == graph[i].length
- 2 <= n <= 300
graph[i][j]是 0 或 1.graph[i][j] == graph[j][i]graph[i][i] == 1- 1 <= initial.length < n
- 0 <= initial[i] <= n - 1
- initial 中每个整数都不同
思路
这个和昨天的题的区别是移除节点之后原来连通的区域可能就断开了。刚开始想，昨天的需要排除掉同一连通区域存在多个感染节点的情况，今天这个就不能排除了。但是其影响的节点数也不能通过连通区域节点个数来计算。处理起来就比较复杂了，不能简单地根据直接相连的节点数来判断。当连通区域中含有多个感染节点时，需要区分边缘感染节点与中间感染节点，边缘感染节点又与孤立的感染节点相同，都是减少1。然后还要考虑连通区域仅有一个感染节点的情况。
区分 单一边缘感染节点 与 孤立感染节点
2、3 感染，返回3
0 - 1
|
3
2
无需区分 多个边缘感染节点 与 孤立感染节点
1、2、3 感染，返回1
0 - 1
|
3
2
区分 中间感染节点 与 孤立感染节点，并且不能仅根据直接相连的非感染节点来判断
0 、2、4、8 感染，返回8
7
| \
0 4 - 6
|
1 - 8 - 3
|
2 5错了好多次，终于调试过了。正面确实不太好求解。总结一下就是：
- 连通区域存在多个感染节点
- 去掉边缘的感染节点，感染节点总数减少1，全是边缘感染节点与包含中间感染节点是一样的
- 去掉非边缘感染节点，需要dfs获取不含感染节点路径的节点总数
- 连通区域仅有1个感染节点（可以是孤立感染节点、边缘节点、中间节点）
- 感染节点总数减少连通区域节点个数
最终答案需要获取以上减少最多的节点，如果存在多个，返回下标最小的。
代码里是按边缘感染节点与中间感染节点分的：
- 边缘感染节点
- 孤立感染节点，减1
- 连通区域内有多个边缘感染节点，减1
- 连通区域内仅有一个边缘感染节点，减连通区域节点个数
- 中间感染节点（如果存在中间节点就不考虑边缘节点了，因为题目中限制了1 <= initial.length < n，一定存在可以减少2个的中间节点，分析到这里时我以为我发现了官网的漏洞，错误的实现也能通过，想要贡献测试用例呢，结果提示测试用例非有效值。如果是小于等于n这个解法就得多一个判断条件initial.length == n，直接取最小下标）
- 仅有一个中间感染节点，连通区域节点个数
- 有多个中间感染节点，dfs搜索不含感染节点路径上的非感染节点个数，如果有感染节点，那么它也是减1，不过这里不再比较了，原因上面也说过了。
代码中d存的是中间节点（包括指向自身的边大于2），如果d为空则表示连通区域全是边缘感染节点（边为2），或孤立感染节点（边为1）。
对于全是边缘感染节点与孤立感染节点的情况，取下标最小即可。而对于中间感染节点，通过dfs来查找连通个数。如果通过dfs查找的个数为1，并且它还是中间感染节点，那么它周围全是感染节点。按道理来说，应该与边缘节点一起取最小下标。但是题目给出了限制，那么一定存在一个可以减少2的中间节点。
通过上面的分析只是说明了该问题正向分析的复杂性，如果不是不断尝试，很难直接把上面的所有情况想清楚。所以，上面的分析也没有太大的用处，过一段时间重做这个题，还是会踩坑。
官网题解使用的是逆向思维，统计的是从每个非感染节点出发不经过感染节点所经历的个数，在dfs过程中使用状态机来标识感染节点的个数。如果只遇到了1个感染节点，那么累加刚才遍历的节点个数，而如果有多个，那么就只能减少它自己。因此，如果存在只遇到一个感染节点的情况，就取个数最大的。否则取下标最小的。
其实，只遇到一个感染节点的情况包括了上面的单一边缘感染节点、中间单一感染节点以及多个中间感染节点（dfs非感染个数不为0的情况，即路径上不含有感染节点）的情况，而遇到多个感染节点，则说明被多个感染节点包围/半包围（对应全是边缘节点、边缘与中间、全中间，后面两种情况上面的算法忽略掉了），并且取最小下标直接包括了孤立感染节点。
可以发现同样是一步处理，我们赋予它不同的内涵，其所应对的场景就大为不同。
代码
/**
* @date 2024-04-17 8:46
*/
public class MinMalwareSpread928 {
public int[] u;
TreeSet<Integer> s;
HashSet<Integer> d = new HashSet<>();
List<Integer>[] g;
public void merge(int x, int y) {
HashSet<Integer> tmp = new HashSet<>();
int rx = find(x, tmp);
int ry = find(y, tmp);
d.addAll(tmp);
if (s.contains(rx) && s.contains(ry)) {
if (rx > ry) {
u[rx] = ry;
} else if (rx < ry) {
u[ry] = rx;
}
} else if (s.contains(ry)) {
u[rx] = ry;
} else {
u[ry] = rx;
}
}
public int find(int x, HashSet<Integer> tmp) {
if (x != u[x]) {
if (s.contains(x) && s.contains(u[x])) {
if (g[x].size() > 2) {
tmp.add(x);
}
if (g[u[x]].size() > 2) {
tmp.add(u[x]);
}
}
x = find(u[x], tmp);
}
return u[x];
}
public int find(int x) {
if (x != u[x]) {
x = find(u[x]);
}
return u[x];
}
public int count(int x) {
int cnt = 0;
int rt = find(x);
for (int i = 0; i < u.length; i++) {
if (rt == find(i)) {
cnt++;
}
}
return cnt;
}
public int countMalware(int x) {
int cnt = 0;
int rt = find(x);
for (int i = 0; i < u.length; i++) {
if (rt == find(i) && s.contains(i)) {
cnt++;
}
}
return cnt;
}
public int adjacencyUninfected(int x, int parent) {
int cnt = 1;
boolean[] visited = new boolean[u.length];
for (Integer node : g[x]) {
if (parent == node || node == x || visited[node]) {
continue;
}
visited = new boolean[u.length];
if (!s.contains(node)) {
int subCnt = dfs(node, x, visited);
if (subCnt != 0) {
cnt += subCnt;
}
}
}
return cnt;
}
public int dfs(int x, int parent, boolean[] visited) {
if (s.contains(x)) {
return 0;
}
int cnt = 1;
for (Integer node : g[x]) {
if (parent == node || node == x || visited[node]) {
visited[node] = true;
continue;
}
visited[node] = true;
if (s.contains(node)) {
return 0;
}
int subCnt = dfs(node, x, visited);
if (subCnt == 0) {
return 0;
} else {
cnt += subCnt;
}
}
return cnt;
}
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
g = new ArrayList[n];
u = new int[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>(n);
u[i] = i;
}
s = new TreeSet<>();
for (int i : initial) {
s.add(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1) {
g[i].add(j);
merge(i, j);
}
}
}
int res = Integer.MAX_VALUE;
int tmp = Integer.MAX_VALUE;
TreeSet<Integer> ini = new TreeSet<>((x, y) -> count(y) - count(x) == 0 ? (adjacencyUninfected(y, -1) - adjacencyUninfected(x, -1) == 0 ? x - y : adjacencyUninfected(y, -1) - adjacencyUninfected(x, -1)) : count(y) - count(x));
if (d.isEmpty()) {
// d为空表示连通区域仅有1个感染节点
for (int i : initial) {
if (countMalware(i) == 1 && count(i) > 1) {
// 连通区域节点数大于1
if (tmp == Integer.MAX_VALUE) {
tmp = i;
} else {
int ci = count(i);
int ct = count(tmp);
if (ci > ct) {
// 取连通区域节点数大的
tmp = i;
} else if (ci == ct) {
// 如果相等取下标小的
tmp = Math.min(i, tmp);
}
}
} else {
// 对于孤立节点，直接取索引最小的即可
res = Math.min(i, res);
}
}
// 如果全部是孤立节点，取res，否则取tmp
return tmp == Integer.MAX_VALUE ? res : tmp;
} else {
ini.addAll(d);
}
return ini.first();
}
}
性能
