8038. Minimum Operations to Collect Elements
给你一个正整数数组 nums 和一个整数 k 。
一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。
请你返回收集元素 1, 2, ..., k 需要的 最少操作次数
测试样例
输入：nums = [3,1,5,4,2], k = 2
输出：4
解释：4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。
解答：按照题意模拟并寻找最小操作次数。
class Solution {
public int minOperations(List<Integer> nums, int k) {
int[] arr = new int[nums.size()];
int offset = 0;
for (int n : nums) {
arr[offset++] = n;
}
boolean[] isUsed = new boolean[k + 1];
int time = 0;
for (int i = arr.length - 1; i >= 0; --i) {
++time;
if (arr[i] < isUsed.length && !isUsed[arr[i]]) {
isUsed[arr[i]] = true;
--k;
if (k == 0) {
return time;
}
}
}
return -1;
}
}100032. Minimum Number of Operations to Make Array Empty
给你一个下标从 0 开始的正整数数组 nums 。
你可以对数组执行以下两种操作 任意次 ：
- 从数组中选择 两个 值 相等 的元素，并将它们从数组中 删除 。
- 从数组中选择 三个 值 相等 的元素，并将它们从数组中 删除 。
请你返回使数组为空的 最少 操作次数，如果无法达成，请返回 -1 。
测试样例：
输入：nums = [2,3,3,2,2,4,2,3,4]
输出：4
解释：
我们可以执行以下操作使数组为空：
- 对下标为 0 和 3 的元素执行第一种操作，得到 nums = [3,3,2,4,2,3,4] 。
- 对下标为 2 和 4 的元素执行第一种操作，得到 nums = [3,3,4,3,4] 。
- 对下标为 0 ，1 和 3 的元素执行第二种操作，得到 nums = [4,4] 。
- 对下标为 0 和 1 的元素执行第一种操作，得到 nums = [] 。
至少需要 4 步操作使数组为空。
解答: 首先利用HashMap将所有相同数字聚合，并且找到每个数字的出现个数。如果有存在出现次数为1的数字，则返回-1.否则利用2和3的整除情况，计算最小次数。
class Solution {
public int minOperations(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
map.put(n, map.getOrDefault(n, 0) + 1);
}
int res = 0;
System.out.println(map);
for (Map.Entry<Integer, Integer> kv : map.entrySet()) {
int val = kv.getValue();
if (val == 1) {
return -1;
}
int div = val / 3, mod = val % 3;
switch (mod) {
case 0:
res += div;
break;
case 1:
div -= 1;
res += div;
res += 2;
break;
case 2:
res += div;
res += 1;
}
}
return res;
}
}100019. Split Array Into Maximum Number of Subarrays
给你一个只包含 非负 整数的数组 nums 。
我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。
请你将数组分割成一个或者更多子数组，满足：
- 每个 元素都 只 属于一个子数组。
- 子数组分数之和尽可能 小 。
请你在满足以上要求的条件下，返回 最多 可以得到多少个子数组。
一个 子数组 是一个数组中一段连续的元素。
测试样例：
输入：nums = [5,7,1,3]
输出：1
解释：
我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。
解答: 如果整个数组取AND结果不为0，那么返回1 （按照AND的要求，更短的子数组是没办法获取比最后结果更小的结果）。如果是0，那么从队尾开始遍历数组，寻找到第一个能使得后缀数组取AND为0的位置。最后从头开始遍历数组，并且贪婪地（AND性质，子数组越长，那么取AND结果是0的可能越大。）寻找最大可能情况。
class Solution {
public int maxSubarrays(int[] nums) {
int sumAnd = nums[0];
for (int n : nums) {
sumAnd &= n;
}
if (sumAnd != 0) {
return 1;
}
sumAnd = nums[nums.length - 1];
int firstZero = nums.length - 1;
for (int i = nums.length - 1; i >= 0; --i) {
sumAnd &= nums[i];
if (sumAnd == 0) {
firstZero = i;
break;
}
}
sumAnd = nums[0];
int res = 0;
for (int i = 0; i < nums.length; ++i) {
sumAnd &= nums[i];
if (sumAnd == 0) {
++res;
if (i + 1 <= firstZero) {
sumAnd = nums[i + 1];
} else {
break;
}
}
}
return res;
}
}8051. Maximum Number of K-Divisible Components
给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个下标从 0 开始长度为 n 的整数数组 values ，其中 values[i] 是第 i 个节点的 值 。再给你一个整数 k 。
你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个 连通块的值 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k 整除，那么我们说这是一个 合法分割 。
请你返回所有合法分割中，连通块数目的最大值 。
测试样例：
输入：n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
输出：2
解释：
我们删除节点 1 和 2 之间的边。这是一个合法分割，因为：
- 节点 1 和 3 所在连通块的值为 values[1] + values[3] = 12 。
- 节点 0 ，2 和 4 所在连通块的值为 values[0] + values[2] + values[4] = 6 。
最多可以得到 2 个连通块的合法分割。
解答: 这道题目难度不大。我们其实需要寻找的是一些边，去除这些边之后，分裂的左右两侧子树仍然被k整除。
class Solution {
private List<Integer>[] edges;
private int[] values;
private int k;
public int maxKDivisibleComponents(int n, int[][] _edges, int[] values, int k) {
edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
this.values = values;
this.k = k;
int[] res = {0};
dfs(0, -1, res);
return res[0];
}
private int dfs(int cur, int pre, int[] res) {
int sum = values[cur] % k;
for (int n : edges[cur]) {
if (n != pre) {
sum = (sum + dfs(n, cur, res)) % k;
}
}
if (sum == 0) {
res[0] += 1;
}
return sum;
}
}