力扣第 441 场周赛

比赛时间 2025-03-16。本场周赛国服共 124 人 AK。

雪竹径公园-甘坑古镇-都市田园-樟坑径线徒步。

T1. 删除后的最大子数组元素和（3 分）

解题思路

答案为 所有非负数去重后的元素和 或者 max(nums)。

时间复杂度：O(n)。

参考代码

class Solution {
    public int maxSum(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int v : nums) {
            if (v > 0) set.add(v);
        }
        if (set.isEmpty()) return Arrays.stream(nums).max().orElseThrow();

        int ans = 0;
        for (Integer v : set) {
            ans += v;
        }
        return ans;
    }
}

T2. 距离最小相等元素查询（4 分）

解题思路

二分查找。

时间复杂度：O(n + qlogn)。

参考代码

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        Map<Integer, List<Integer>> posMp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            posMp.computeIfAbsent(nums[i], e -> new ArrayList<>()).add(i);
        }
        for (List<Integer> p : posMp.values()) {
            // 前后各加一个哨兵
            int i0 = p.getFirst();
            p.addFirst(p.getLast() - n);
            p.add(i0 + n);
        }

        List<Integer> ans = new ArrayList<>();
        for (int qi : queries) {
            List<Integer> p = posMp.get(nums[qi]);
            if (p.size() == 3) {
                ans.add(-1);
            } else {
                int j = Collections.binarySearch(p, qi); // 二分
                ans.add(Math.min(qi - p.get(j - 1), p.get(j + 1) - qi));
            }
        }
        return ans;
    }
}

T3. 零数组变换 IV（5 分）

解题思路

0-1 背包。

时间复杂度：O(qnU)。

参考代码

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        if (Arrays.stream(nums).allMatch(x -> x == 0)) return 0; // nums 全为 0

        int n = nums.length;
        boolean[][] f = new boolean[n][];
        for (int i = 0; i < n; i++) {
            f[i] = new boolean[nums[i] + 1];
            f[i][0] = true;
        }

        for (int k = 0; k < queries.length; k++) {
            int[] q = queries[k];
            int val = q[2];
            for (int i = q[0]; i <= q[1]; i++) {
                if (f[i][nums[i]]) continue; // 小优化：已经满足要求，不计算
                for (int j = nums[i]; j >= val; j--) {
                    f[i][j] = f[i][j] || f[i][j - val];
                }
            }
            // if all Ture
            boolean ok = true;
            for (int i = 0; i < n; i++) {
                if (!f[i][nums[i]]) {
                    ok = false;
                    break;
                }
            }
            if (ok) return k + 1;
        }
        return -1;
    }
}

T4. 统计美丽整数的数目（8 分）

解题思路

数位 DP。和 2827 题 几乎是一样的题目，

时间复杂度：O(10^2 * 81 * 81) = O(656100)。

参考代码

class Solution {
    private int k;

    public int beautifulNumbers(int l, int r) {
        // 数字之和 [1, 9*9] = [1,81]
        int ans = 0;
        for (int k = 1; k <= 81; k++) {
            int res = numberOfBeautifulIntegers(l, r, k);
            ans += res;
        }
        return ans;
    }

    public int numberOfBeautifulIntegers(int low, int high, int k) {
        this.k = k;
        int ans1 = count(low - 1);
        int ans2 = count(high);
        return ans2 - ans1;
    }

    private char[] s;
    private int[][][] dp;

    private int count(int num) {
        s = String.valueOf(num).toCharArray();
        int n = String.valueOf(num).length();
        dp = new int[n][k][82];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return f(0, 1, 0, true, false);
    }

    // remain:%k的余数
    private int f(int i, int remain, int digitSum, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return (isNum && remain == 0 && digitSum == k) ? 1 : 0;
        }
        if (!isLimit && isNum && dp[i][remain][digitSum] != -1) {
            return dp[i][remain][digitSum];
        }
        int ans = 0;
        if (!isNum) {
            ans += f(i + 1, remain, digitSum, false, false);
        }
        int down = isNum ? 0 : 1;
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = down; d <= up; d++) {
            ans += f(i + 1, remain * d % k, digitSum + d, isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i][remain][digitSum] = ans;
        }
        return ans;
    }
}

（全文完）