力扣第 122 场双周赛

比赛时间 2024-01-20。本场周赛国服共 150 人 AK。

T1. 将数组分成最小总代价的子数组 I（3 分）

解题思路

贪心。nums[1:] 部分取最小的两个数，加上 nums[0]。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int minimumCost(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums, 1, n);
        return nums[0] + nums[1] + nums[2];
    }
}

T2. 判断一个数组是否可以变为有序（4 分）

解题思路

分组循环。排序模拟。再判断整个数组是否有序即可。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int st = i;
            for (i++; i < n && Integer.bitCount(nums[i]) == Integer.bitCount(nums[i - 1]); i++) {
            }
            Arrays.sort(nums, st, i);
        }

        for (int j = 1; j < n; j++) {
            if (nums[j - 1] > nums[j]) return false;
        }
        return true;
    }
}

T3. 通过操作使数组长度最小（5 分）

解题思路

脑筋急转弯。

假设 a < b，那么 a % b = a，意味着小数可以无损消除大数。直接计算最小数的频次 c，返回 (c + 1) / 2，不出意外 wa 了。

注意到可能由 b % a 得到比 a 小的非零数，这种情况，最小数频次变为 1，答案为 1。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minimumArrayLength(int[] nums) {
        int mn = Arrays.stream(nums).min().orElseThrow();
        int c = 0;
        for (int v : nums) {
            if (v == mn) c++;
            if (v % mn > 0) {
                return 1;
            }
        }
        return (c + 1) / 2;
    }
}

T4. 将数组分成最小总代价的子数组 II（7 分）

解题思路

滑动窗口 + 双平衡树模拟 multiset。注意优先队列删除指定元素时间复杂度是 O(n)，除非用懒删除堆，不过比较复杂。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public long minimumCost(int[] nums, int k, int dist) {
        int n = nums.length;
        // 窗口大小 m，前 k-1 小的和，等价于 总和减去前 m-(k-1) 大的和
        int m = dist + 1;
        MultiSets multiSets = new MultiSets(m, m - (k - 1));
        for (int i = 1; i < m + 1; i++) {
            multiSets.add(nums[i]);
        }
        long ans = multiSets.tot - multiSets.sumX;
        for (int i = m + 1; i < n; i++) {
            multiSets.add(nums[i]);
            multiSets.del(nums[i - m]);

            ans = Math.min(ans, multiSets.tot - multiSets.sumX);
        }
        return ans + nums[0];
    }

    private static class MultiSets {
        int n, k;
        TreeMap<Integer, Integer> xMap, yMap;
        int xsz, ysz;
        long sumX, tot;

        // n:窗口大小, k:第 k 大
        public MultiSets(int n, int k) {
            this.n = n;
            this.k = k;
            this.xMap = new TreeMap<>();
            this.yMap = new TreeMap<>();
            this.xsz = 0;
            this.ysz = 0;
            sumX = 0;
        }

        private void add(int v) {
            yInsertV(v);
            balance();
            tot += v;
        }

        private void del(int v) {
            if (xMap.containsKey(v)) {
                xEraseV(v);
            } else {
                yEraseV(v);
            }
            balance();
            tot -= v;
        }

        private void balance() {
            if (xsz + ysz < n) return;
            while (xsz < k) {
                int iy = yMap.lastKey();
                yEraseV(iy);
                xInsertV(iy);
            }
            if (xsz == 0 || ysz == 0) return;
            while (true) {
                int ix = xMap.firstKey();
                int iy = yMap.lastKey();
                if (ix >= iy) break;
                xEraseV(ix);
                yEraseV(iy);
                xInsertV(iy);
                yInsertV(ix);
            }
        }

        private void xInsertV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) + 1);
            xsz++;
            sumX += v;
        }

        private void yInsertV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) + 1);
            ysz++;
        }

        private void xEraseV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) - 1);
            if (xMap.get(v) == 0) xMap.remove(v);
            xsz--;
            sumX -= v;
        }

        private void yEraseV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) - 1);
            if (yMap.get(v) == 0) yMap.remove(v);
            ysz--;
        }
    }
}

（全文完）