标签： 动态规划

目标

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。

返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。

示例 1：

输入：nums = [3,4,1,2,6], queries = [[0,4]]
输出：[false]
解释：
子数组是 [3,4,1,2,6]。2 和 6 都是偶数。

示例 2：

输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
输出：[false,true]
解释：
子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

思路

类似于特殊数组I，只不过是判断子数组是否是特殊数组。我们可以记录奇偶性相同的下标，如果 queries[i] = [fromi, toi] 包含其中的下标对返回false。但是如果所有元素的奇偶性都相同，下标对有n个，查询也是n次，O(n^2) 对于 10^5 的数据规模会超时。

我们可以将问题转化一下，由于仅考虑相邻元素的奇偶性，将数组中的偶数元素都替换为0，奇数元素都替换为1，这样0与1交替出现的是特殊数组。使用前缀和判断不了是否交替出现，只能初步排除一些区间。

之所以超时是因为进行了许多重复判断，我们想直接判断查询区间是否包含奇偶相同的下标对。可以使用二分查找，如果查出的from，to下标相同，说明不相交。

这里比较坑的一点是，题目中没有说明如果查询区间只包含一个值视为奇偶性不同。

log2(10^5) ≈ 16.6 时间复杂度为O(nlogn)，耗时30ms，说明10^6的数据规模，O(n)的解法不会超时，以后多留意一下。

看了题解，其实可以使用前缀和，只不过不是将原数组转为0或1计算前缀和，而是定义数组diff，原数组nums相邻元素奇偶性相同为0，不同为1。对应给定的区间，我们就可以根据diff的前缀和判断是否含有奇偶性相同的元素。时间复杂度为O(n)，耗时3ms。

也有使用动态规划求解的，记录最近一次奇偶性相同的位置。时间复杂度为O(n)，耗时3ms。

代码

/**
 * @date 2024-08-14 9:58
 */
public class IsArraySpecial3152 {

    public boolean[] isArraySpecial_v1(int[] nums, int[][] queries) {
        int n = nums.length;
        List<Integer> from = new ArrayList<>();
        List<Integer> to = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            if (nums[i] % 2 == nums[j] % 2) {
                from.add(j);
                to.add(i);
            }
        }
        int l = from.size();
        int[] fromArray = new int[l];
        int[] toArray = new int[l];
        for (int i = 0; i < l; i++) {
            fromArray[i] = from.get(i);
            toArray[i] = to.get(i);
        }
        int length = queries.length;
        boolean[] res = new boolean[length];
        Arrays.fill(res, true);
        for (int i = 0; i < length; i++) {
            int[] query = queries[i];
            if (query[0] == query[1]) {
                // 如果查询区间相同认为是特殊区间
                res[i] = true;
                continue;
            }
            int fromIndex = Arrays.binarySearch(fromArray, query[0]);
            if (fromIndex >= 0) {
                // 如果需要查询的数组包含了query[0]，由于前面判断了相等的情况，
                // 执行到这里query[1] > query[0]，而对应的toIndex 为 fromIndex + 1，
                // 推出 query[1] >= toIndex，说明包含奇偶性相同的下标对，
                res[i] = false;
                continue;
            }
            int toIndex = Arrays.binarySearch(toArray, query[1]);
            if (fromIndex != toIndex) {
                // 执行到这里，fromIndex < 0，如果 toIndex >= 0，由于 query[0] < query[1]，推出 query[0] <= fromIndex
                // 如果 toIndex < 0，说明查询区间开始与结束下标都没有找到，
                // 如果插入位置不同，说明也包含了奇偶性相同的元素
                res[i] = false;
            }
        }
        return res;
    }

}

性能

目标

现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。

给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。

返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。

k 个数字的 平均值 为这些数字求和后再除以 k 。

注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。

示例 1：

输入：rolls = [3,2,4,3], mean = 4, n = 2
输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。

示例 2：

输入：rolls = [1,5,6], mean = 3, n = 4
输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。

示例 3：

输入：rolls = [1,2,3,4], mean = 6, n = 4
输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。

示例 4：

输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。

说明：

• m == rolls.length
• 1 <= n, m <= 10^5
• 1 <= rolls[i], mean <= 6

思路

已知 m+n 个投骰子的观测数据的均值 mean，以及其中 m 个观察数据 rolls，返回缺失的观测数据，如果存在多个只返回其中一组，如果不存在答案返回空数组。

我们可以很容易计算出观测数据的总和 mean * (m + n)，用它减去已知的观测数据和 sum，得到 diff。

• 如果 diff > n * 6 说明 剩余的 n 次都得到 6 点也不够，返回空数组。
• 如果 diff < n 说明 剩余的 n 次都得到 1 点也多余，返回空数组。
• 否则，问题变成选 n 个数字使其和等于 diff，每个数的取值范围是 1 ~ 6。

这让我想起了背包问题还有之前做过的硬币找零，组合总和等问题。这里只需要返回一种可能就行了，不需要动态规划。

可以先计算 val = diff / n，如果有剩余 r，就为 r 个值加1。

代码

/**
 * @date 2024-05-27 9:20
 */
public class MissingRolls2028 {

    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int sum = 0;
        for (int roll : rolls) {
            sum += roll;
        }
        int diff = mean * (m + n) - sum;
        if (diff > n * 6 || diff < n) {
            return new int[0];
        }
        int[] res = new int[n];
        int val = diff / n;
        diff = diff - val * n;
        Arrays.fill(res, val);
        for (int i = 0; i < diff; i++) {
            res[i]++;
        }
        return res;
    }
}

性能