Biweekly Contest 122

100181. Divide an Array Into Subarrays With Minimum Cost I

给你一个长度为 n 的整数数组 nums 。

一个数组的 代价 是它的 第一个 元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。

你需要将 nums 分成 3 个 连续且没有交集 的子数组。

请你返回这些子数组的 最小 代价 总和 。

测试样例：

输入：nums = [1,2,3,12]

输出：6

解释：最佳分割成 3 个子数组的方案是：[1] ，[2] 和 [3,12] ，总代价为 1 + 2 + 3 = 6 。其他得到 3 个子数组的方案是：

• [1] ，[2,3] 和 [12] ，总代价是 1 + 2 + 12 = 15 。
• [1,2] ，[3] 和 [12] ，总代价是 1 + 3 + 12 = 16 。

解答：第一个数必须留着，然后寻找之后的数字里面最小的2个就行（注意这点，第四题需要明白为啥）。

class Solution {
    public int minimumCost(int[] nums) {
        int res = nums[0];
        int[] best = {Integer.MAX_VALUE, Integer.MAX_VALUE};
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] < best[0]) {
                best[1] = best[0];
                best[0] = nums[i];
            } else if (nums[i] < best[1]) {
                best[1] = nums[i];
            }
        }
        return nums[0] + best[1] + best[0];
    }
}

100199. Find if Array Can Be Sorted

给你一个下标从 0 开始且全是 正 整数的数组 nums 。

一次 操作 中，如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。

如果你可以使数组变有序，请你返回 true ，否则返回 false 。

测试样例：

输入：nums = [8,4,2,30,15]

输出：true

解释：我们先观察每个元素的二进制表示。 2 ，4 和 8 分别都只有一个数位为 1 ，分别为 "10" ，"100" 和 "1000" 。15 和 30 分别有 4 个数位为 1 ："1111" 和 "11110" 。我们可以通过 4 个操作使数组有序：

• 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
• 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
• 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
• 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ，数组变为 [2,4,8,15,30] 。

数组变成有序的，所以我们返回 true 。注意我们还可以通过其他的操作序列使数组变得有序。

解答：这道题目范围极小，可以直接暴力。类似冒泡排序的思路，当前数左边所有比它小的数字都能和它交换，那么数组就能变的有序。

class Solution {
    public boolean canSortArray(int[] nums) {
        int[] bitCounts = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            bitCounts[i] = bitCount(nums[i]);
        }
        for (int i = 0; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] < nums[j] && bitCounts[i] != bitCounts[j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private int bitCount(int n) {
        int res = 0;
        while (n > 0) {
            res += (n & 1);
            n = n >> 1;
        }
        return res;
    }
}

100164. Minimize Length of Array Using Operations

给你一个下标从 0 开始的整数数组 nums ，它只包含 正 整数。

你的任务是通过进行以下操作 任意次 （可以是 0 次） 最小化 nums 的长度：

• 在 nums 中选择 两个不同 的下标 i 和 j ，满足 nums[i] > 0 且 nums[j] > 0 。
• 将结果 nums[i] % nums[j] 插入 nums 的结尾。
• 将 nums 中下标为 i 和 j 的元素删除。

请你返回一个整数，它表示进行任意次操作以后 nums 的 最小长度 。

测试样例：

输入：nums = [1,4,3,1]

输出：1

解释：使数组长度最小的一种方法是：

• 操作 1 ：选择下标 2 和 1 ，插入 nums[2] % nums[1] 到数组末尾，得到 [1,4,3,1,3] ，然后删除下标为 2 和 1 的元素。nums 变为 [1,1,3] 。
• 操作 2 ：选择下标 1 和 2 ，插入 nums[1] % nums[2] 到数组末尾，得到 [1,1,3,1] ，然后删除下标为 1 和 2 的元素。nums 变为 [1,1] 。
• 操作 3 ：选择下标 1 和 0 ，插入 nums[1] % nums[0] 到数组末尾，得到 [1,1,0] ，然后删除下标为 1 和 0 的元素。nums 变为 [0] 。

nums 的长度无法进一步减小，所以答案为 1 。1 是可以得到的最小长度。

解答：没啥意思的脑筋急转弯题。需要先先到一点如果A > B，那么A % B < B，并且B % A == B。首先寻找当前数组的最小值，如果最小值的出现数字小于等于2，那么一切都好，答案是1（根据第一个规则，所有数都是最小数%大数，留下小数。小数的出现数小于2，那么答案必然是1）。否则，我们寻找任意一个大数，如果这个大数不能被最小数整除，那么一切安好，出现了新的最小数，答案也是1。最差的情况就是找不到，那么任何大数都是k*最小数，无论怎么取模，都会归于最小数。这个情况，出现次数就是最小数22变0。

class Solution {
    public int minimumArrayLength(int[] nums) {
        int min = Integer.MAX_VALUE;
        int count = 0;
        for (int n : nums) {
            if (n < min) {
                min = n;
                count = 1;
            } else if (n == min) {
                count += 1;
            }
        }
        if (count <= 2) {
            return 1;
        }
        for (int n : nums) {
            if (n % min != 0) {
                return 1;
            }
        }
        return count / 2 + (count % 2);
    }
}

100178. Divide an Array Into Subarrays With Minimum Cost II

给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。

一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。

你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。

请你返回这些子数组的 最小 总代价。

测试样例：

输入：nums = [10,1,2,2,2,1], k = 4, dist = 3

输出：15

解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。15 是分割成 4 个子数组的最小总代价。

解答：这题本质上，就是寻找区间上，最小的k-1个数（第一个数一定会被算进来）。有dist这个限制，那么区间就被锁死了。我们可以用双指针，配合2个优选队列来寻找最佳的k - 1个数（能挑到k - 1个数，那么必然可以分成k - 1个区间）。

class Solution {
    private class CustomMap {
        TreeMap<Integer, Integer> map;
        int size;
        long sum;

        public CustomMap() {
            map = new TreeMap<>();
            size = 0;
            sum = 0;
        }

        public boolean removeKey(int key) {
            if (map.containsKey(key)) {
                int c = map.get(key);
                if (c == 1) {
                    map.remove(key);
                } else {
                    map.put(key, c - 1);
                }
                sum -= key;
                size -= 1;
            }
            return false;
        }

        public void addKey(int key) {
            ++size;
            sum += key;
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        public int firstKey() {
            return map.firstKey();
        }

        public int lastKey() {
            return map.lastKey();
        }
    }

    public long minimumCost(int[] nums, int k, int dist) {
        long res = Long.MAX_VALUE;
        CustomMap effective = new CustomMap(), nonEffective = new CustomMap();
        int secondGroupStart = 1;
        for (int i = 1; i < nums.length; ++i) {
            nonEffective.addKey(nums[i]);
            giveUpFirstKey(effective, nonEffective);
            if (i - secondGroupStart > dist) {
                if (!nonEffective.removeKey(nums[secondGroupStart])) {
                    effective.removeKey(nums[secondGroupStart]);
                    giveUpFirstKey(effective, nonEffective);
                }
                ++secondGroupStart;
            }
            while (effective.size > k - 1) {
                giveLastKey(effective, nonEffective);
            }
            if (effective.size == k - 1) {
                res = Math.min(res, effective.sum + nums[0]);
            }
        }
        return res;
    }

    private void giveUpFirstKey(CustomMap effective, CustomMap nonEffective) {
        if (!nonEffective.map.isEmpty()) {
            int firstKey = nonEffective.firstKey();
            effective.addKey(firstKey);
            nonEffective.removeKey(firstKey);
        }
    }

    private void giveLastKey(CustomMap effective, CustomMap nonEffective) {
        int lastKey = effective.lastKey();
        effective.removeKey(lastKey);
        nonEffective.addKey(lastKey);
    }
}