100111. Find the K-or of an Array
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
nums 中的 K-or 是一个满足以下条件的非负整数：
- 只有在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值才是 1 。
返回 nums 的 K-or 值。
注意 ：对于整数 x ，如果 (2i AND x) == 2i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。
测试样例：
输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：
nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。
nums[0] 和 nums[5] 的第 1 位的值为 1 。
nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。
nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。
只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此，答案为 2^0 + 2^3 = 9 。
解答：这题就是利用暴力运算，位统计一下。
class Solution {
public int findKOr(int[] nums, int k) {
int res = 0;
for (int i = 0; i < 31; ++i) {
int count = 0;
for (int n : nums) {
int mark = (n >> i) & 1;
count += mark;
}
if (count >= k) {
res += (1 << i);
}
}
return res;
}
}100102. Minimum Equal Sum of Two Arrays After Replacing Zeros
给你两个由正整数和 0 组成的数组 nums1 和 nums2 。
你必须将两个数组中的 所有 0 替换为 严格 正整数，并且满足两个数组中所有元素的和 相等 。
返回 最小 相等和 ，如果无法使两数组相等，则返回 -1 。
测试样例：
输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：
可以按下述方式替换数组中的 0 ：
- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。
- 用 1 替换 nums2 中的一个 0 。得到 nums2 = [6,5,1] 。
两个数组的元素和相等，都等于 12 。可以证明这是可以获得的最小相等和。
解答：这道题目需要分类讨论一下。当nums1和nums2不存在0的时候，需要特殊判断一下。否则就取两者最小可能值的max。
class Solution {
public long minSum(int[] nums1, int[] nums2) {
int zc1 = 0, zc2 = 0;
long sum1 = 0, sum2 = 0;
for (int n : nums1) {
sum1 += n;
if (n == 0) {
++zc1;
}
}
for (int n : nums2) {
sum2 += n;
if (n == 0) {
++zc2;
}
}
long m1 = sum1 + zc1, m2 = zc2 + sum2;
if (zc1 == 0 && m2 > sum1) {
return -1;
}
if (zc2 == 0 && m1 > sum2) {
return -1;
}
if (zc1 == 0 && zc2 == 0 && sum1 != sum2) {
return -1;
}
return Math.max(m1, m2);
}
}100107. Minimum Increment Operations to Make Array Beautiful
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。
你可以执行下述 递增 运算 任意 次（可以是 0 次）：
- 从范围 [0, n - 1] 中选则一个下标 i ，并将 nums[i] 的值加 1 。
如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。
以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。
子数组是数组中的一个连续 非空 元素序列。
测试样例：
输入：nums = [2,3,0,0,2], k = 4
输出：3
解释：
可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 1 ，并且将 nums[1] 的值加 1 -> [2,4,0,0,2] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,3] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,4] 。
长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。
在所有子数组中，最大元素都等于 k = 4 ，所以 nums 现在是美丽数组。
可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。
因此，答案为 3 。
解答：这道题目需要利用动态规划。长度等于3的子数组最难满足（子数组越长，包含的数字越多，那么max大于等于k的概率肯定就越大）。接下来就是看怎么利用动态规划了，其实逻辑也很简单，长度为3的数组，我们只要看让第i位大于等于k的最小操作次数。然后滑动窗口向下之后，之前的第1位，就是新数组的第0位，之前的第二位就是新数组的第1位。以此类推计算，就能获取最小值。
class Solution {
public long minIncrementOperations(int[] nums, int k) {
long[] dp = new long[3];
for (int i = 2; i >= 0; --i) {
dp[i] = Math.max(0, k - nums[i]);
if (i != 2) {
dp[i] = Math.min(dp[i], dp[i + 1]);
}
}
for (int i = 1; i + 3 <= nums.length; ++i) {
long[] nextDp = {dp[1], dp[2], Long.MAX_VALUE};
long min = dp[0];
for (int j = 2; j >= 0; --j) {
nextDp[j] = Math.min(nextDp[j], min + Math.max(0, k - nums[i + j]));
if (j != 2) {
nextDp[j] = Math.min(nextDp[j], nextDp[j + 1]);
}
}
dp = nextDp;
}
return dp[0];
}
}100108. Maximum Points After Collecting Coins From All Nodes
节点 0 处现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。
从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。
节点 i 上的金币可以用下述方法之一进行收集：
- 收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。
- 收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。
返回收集 所有 树节点的金币之后可以获得的最大积分。
测试样例
输入：edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
输出：11
解释：
使用第一种方法收集节点 0 上的所有金币。总积分 = 10 - 5 = 5 。
使用第一种方法收集节点 1 上的所有金币。总积分 = 5 + (10 - 5) = 10 。
使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) = 1 ，总积分 = 10 + floor(3 / 2) = 11 。
使用第二种方法收集节点 3 上的所有金币。总积分 = 11 + floor(1 / 2) = 11.
可以证明收集所有节点上的金币能获得的最大积分是 11 。
解答：也是很标准的动态规划题目。因为操作2会传播，但是coins[i]其实是有上限的，所以最多的节点操作数是14次。我们利用动态规划记录当前操作数下，最佳的结果。
class Solution {
private List<Integer>[] edges;
private int[] coins;
private int k;
private Integer[][] mem;
public int maximumPoints(int[][] _edges, int[] coins, int k) {
this.edges = new List[coins.length];
for (int i = 0; i < coins.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
this.k = k;
this.coins = coins;
this.mem = new Integer[coins.length][15];
return helper(0, 0, -1);
}
private int helper(int pos, int time, int last) {
time = Math.min(time, 14);
if (mem[pos][time] == null) {
int coin = curCoin(coins[pos], time);
int s1 = 0, s2 = 0;
for (int n : edges[pos]) {
if (n != last) {
s1 += helper(n, time, pos);
s2 += helper(n, time + 1, pos);
}
}
mem[pos][time] = Math.max(s1 + coin - k, s2 + coin / 2);
}
return mem[pos][time];
}
private int curCoin(int coin, int time) {
for (int i = 0; i < time; ++i) {
coin /= 2;
}
return coin;
}
}