力扣第 376 场周赛

比赛时间 2023-12-17。本场周赛国服共 197 人 AK。

T1. 找出缺失和重复的数字（3 分）

解题思路

计数。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int n2 = n * n;
        int[] cnt = new int[n2 + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cnt[grid[i][j]]++;
            }
        }
        int[] ans = new int[2];
        for (int i = 1; i <= n2; i++) {
            if (cnt[i] == 2) {
                ans[0] = i;
            } else if (cnt[i] == 0) {
                ans[1] = i;
            }
        }
        return ans;
    }
}

T2. 划分数组并满足最大差限制（4 分）

解题思路

贪心，最小差出现在有序数组中，因此排序后遍历即可。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int[][] ans = new int[n / 3][3];
        for (int i = 0; i < n; i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][];
            }
            ans[i / 3][0] = nums[i];
            ans[i / 3][1] = nums[i + 1];
            ans[i / 3][2] = nums[i + 2];
        }
        return ans;
    }
}

T3. 使数组成为等数数组的最小代价（5 分）

解题思路

回文根 + 中位数。

先将 1e10 内的回文数预处理出来。要使总代价尽可能小，那越接近中位数越好，二分加速找到对应回文数下标 取最小值。

时间复杂：O(nlogn)。

参考代码

class Solution {
    static List<Long> pal;

    static {
        // size = 199998, max = 9999999999
        pal = new ArrayList<>();
        for (int L = 1; L <= 5; L++) {
            int low = (int) Math.pow(10, L - 1);
            int high = (int) Math.pow(10, L);
            // Check for odd-length palindromes
            for (int root = low; root < high; root++) {
                StringBuilder sb = new StringBuilder(String.valueOf(root));
                for (int k = L - 2; k >= 0; k--) {
                    sb.append(sb.charAt(k));
                }
                long x = Long.parseLong(sb.toString());
                pal.add(x);
            }
            // Check for even-length palindromes
            for (int root = low; root < high; root++) {
                StringBuilder sb = new StringBuilder(Integer.toString(root));
                for (int k = L - 1; k >= 0; k--) {
                    sb.append(sb.charAt(k));
                }
                long x = Long.parseLong(sb.toString());
                pal.add(x);
            }
        }
        pal.sort(null);
    }

    public long minimumCost(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        long median = nums[n / 2];
        int i = lowerBound(pal, median);
        long ans = Long.MAX_VALUE;
        for (int j = Math.max(0, i - 1); j <= i + 1; j++) {
            long y = pal.get(j);
            ans = Math.min(ans, getCost(nums, y));
        }
        return ans;
    }

    private long getCost(int[] nums, long y) {
        long cost = 0;
        for (int v : nums) {
            cost += Math.abs(y - v);
        }
        return cost;
    }

    private int lowerBound(List<Long> a, long key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

T4. 执行操作使频率分数最大（6 分）

解题思路

双指针 / 滑动窗口 + 中位数 贪心。

窗口内操作次数最小是变为中位数，当操作次数大于 k 时，收缩窗口（左指针右移），答案即为窗口最大长度。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int maxFrequencyScore(int[] nums, long k) {
        int n = nums.length;
        Arrays.sort(nums);
        long[] ps = new long[n + 1];
        for (int i = 0; i < n; i++) {
            ps[i + 1] = ps[i] + nums[i];
        }

        int l = 0, r = 0;
        int ans = 0;
        while (r < n) {
            while (getCost(nums, l, r, ps) > k) {
                l++;
            }
            // 代价 <= k
            ans = Math.max(ans, r - l + 1);

            r++;
        }
        return ans;
    }

    private long getCost(int[] nums, int l, int r, long[] ps) {
        // 中位数下标 (l+r)/2
        long median = nums[(l + r) / 2];
        // 左 [l, (l+r)/2 -1], 和 ps[(l+r)/2] - ps[l], 个数 (l+r)/2 -1-l+1 = (l+r)/2 -l
        int leftLen = (l + r) / 2 - l;
        long leftSum = ps[(l + r) / 2] - ps[l];
        // 右 [(l+r)/2 +1, r], 和 ps[r+1]-ps[(l+r)/2 +1], 个数 r-((l+r)/2 +1)+1
        int rightLen = r - ((l + r) / 2 + 1) + 1;
        long rightSum = ps[r + 1] - ps[(l + r) / 2 + 1];
        return (median * leftLen - leftSum) + (rightSum - median * rightLen);
    }
}

（全文完）