第 369 场力扣周赛

找出数组中的 K-or 值

模拟。

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < 31; i++) {
            int cnt = 0;
            for (int x : nums) {
                cnt += x >> i & 1;
            }
            if (cnt >= k) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

数组的最小相等和

分类讨论。所有 \(0\) 都必须被替换为正整数，那么首先将所有 \(0\) 替换为 \(1\)。如果两个数组中都有 \(0\)，则此时得到的最大的数组和就应该是答案，因为较小的一方总是可以使用更大的正整数替换 \(0\)，使得两个数组的元素和相等。如果某个数组的和不等于最大和，并且数组中不包含 \(0\)，那么就无法使两个数组的元素和相等。

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        int cnt1 = 0, cnt2 = 0;
        long sum1 = 0L, sum2 = 0L;
        for (int x : nums1) {
            if (x == 0) cnt1++;
            sum1 += x;
        }
        for (int x : nums2) {
            if (x == 0) cnt2++;
            sum2 += x;
        }
        long max = Math.max(sum1 + cnt1, sum2 + cnt2);
        if (sum1 != max && cnt1 == 0) return -1;
        if (sum2 != max && cnt2 == 0) return -1;
        return max;
    }
}

使数组变美的最小增量运算数

按照灵神的题解，每个位置的状态就是它右边有多少个数小于 \(k\)，加上这个维度就可以做记忆化搜索，然后转递推真的很妙。题解区还有其他的状态定义方式，可以看看。代码就贴灵神的。（这题感觉很不错，没有见过的类型）

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        long f0 = 0, f1 = 0, f2 = 0;
        for (int x : nums) {
            long inc = f0 + Math.max(k - x, 0);
            f0 = Math.min(inc, f1);
            f1 = Math.min(inc, f2);
            f2 = inc;
        }
        return f0;
    }
}

收集所有金币可获得的最大积分

当我们遍历到某个节点时，它的状态就是需要除以多少次 \(2\)，由数据范围可知每个节点最多有 \(15\) 个状态。我们可以从子问题的最优解推出原问题的最优解，并且子问题可以独立求解，符合最优子结构；如果当前节点处于某个状态，它可能是由不同的路径转移得到的，即存在重叠子问题。所以我们可以使用树型 DP 求解该问题，列出如下状态转移方程：

$$ dp[x][i]=\max(\sum_{y}{dp[y][i]}+(coins[x]>>i)-k,\sum_{y}{dp[y][i + 1]}+(coins[x]>>(i+1))) $$

其中 \(dp[i][j]\) 表示到达节点 \(i\)，需要除以 \(2^{j}\)，该状态下以节点 \(i\) 为根的子树能够得到的最大积分。

class Solution {
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, t -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        return dfs(0, -1, g, coins, k)[0];
    }
    
    private int[] dfs(int x, int fa, List<Integer>[] g, int[] coins, int k) {
        int[] sum1 = new int[15];
        int[] sum2 = new int[15];

        for (int y : g[x]) {
            if (y == fa) continue;
            int[] t = dfs(y, x, g, coins, k);
            for (int i = 0; i < 14; i++) {
                sum1[i] += t[i];
                sum2[i] += t[i + 1];
            }
        }

        for (int i = 0; i < 14; i++) {
            sum1[i] = Math.max(sum1[i] + (coins[x] >> i) - k, sum2[i] + (coins[x] >> (i + 1)));
        }
        return sum1;
    }
}