力扣第 369 场周赛

比赛时间 2023-10-29。本场周赛国服共 255 人 AK。

T1. 找出数组中的 K-or 值（3 分）

解题思路

拆位 + 模拟。

时间复杂度：O(nlogU)。

参考代码

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

T2. 数组的最小相等和（4 分）

解题思路

贪心。由于 0 要替换为正整数，因此最小也要替换为 1，求出最小上界，然后判断是否是合法解即可。

时间复杂度：O(n)。

参考代码

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        long s1 = 0, s2 = 0, c0_1 = 0, c0_2 = 0;
        for (int x : nums1) {
            if (x == 0) {
                c0_1++;
            } else {
                s1 += x;
            }
        }
        for (int x : nums2) {
            if (x == 0) {
                c0_2++;
            } else {
                s2 += x;
            }
        }
        long up = Math.max(s1 + c0_1, s2 + c0_2);
        if (up > s1 && c0_1 == 0) return -1;
        if (up > s2 && c0_2 == 0) return -1;
        return up;
    }
}

T3. 使数组变美的最小增量运算数（5 分）

解题思路

记忆化搜索，从下标 2 开始。

时间复杂度：O(n)。

参考代码

class Solution {
    private int[] nums;
    private int n, k;
    private long[] memo;

    public long minIncrementOperations(int[] nums, int k) {
        this.nums = nums;
        this.n = nums.length;
        this.k = k;

        memo = new long[n];
        Arrays.fill(memo, -1);
        return dfs(2);
    }

    private long dfs(int i) {
        if (i >= n) return 0;
        if (memo[i] != -1) return memo[i];

        long res = (long) 1e18;
        for (int j = i; j >= i - 2; j--) {
            res = Math.min(res, dfs(j + 3) + Math.max(0, k - nums[j]));
        }
        return memo[i] = res;
    }
}

T4. 收集所有金币可获得的最大积分（6 分）

解题思路

树形 DP + 记忆化搜索 + 剪枝。注意到有一个剪枝上界。

一开始写法是 b * 2（不连续、稀疏），用哈希表做记忆化，TLE；后来优化为 记录 b 右移的位数（连续），用数组做记忆化，AC。。

时间复杂度：O(n)。

参考代码

class Solution {
    private int[] coins;
    private int k;
    private List<Integer>[] g;
    private int[][] memo;

    public int maximumPoints(int[][] edges, int[] coins, int k) {
        this.coins = coins;
        this.k = k;

        int n = edges.length + 1;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        // 2^14 = 16384 > 1e4
        memo = new int[15][n];
        for (int i = 0; i < 15; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(0, -1, 0);
    }

    // 右移 >> b
    private int dfs(int x, int fa, int b) {
        if (b > 14) return 0;
        if (memo[b][x] != -1) return memo[b][x];

        int s1 = (coins[x] >> b) - k;
        int s2 = (coins[x] >> (b + 1));
        for (Integer y : g[x]) {
            if (y != fa) {
                s1 += dfs(y, x, b);
                s2 += dfs(y, x, b + 1);
            }
        }
        int res = Math.max(s1, s2);
        memo[b][x] = res;
        return res;
    }
}

（全文完）