3152. 特殊数组 II

题目描述 中等

信息

题目来源：LeetCode官网题目

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

你有一个整数数组 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 <= 105
• 1 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

题解

本题可以参考前缀和的思路，先遍历一次数组，计算前缀和。 在本题里，假设每单个元素的前缀和为1，

• 如果 nums[i] 与左边相邻的元素 nums[i−1] 奇偶性相同，则此时 dp[i]=1;
• 如果 nums[i] 与左边相邻的元素 nums[i−1] 奇偶性不同，则此时特殊数组长度加一 dp[i]=dp[i−1]+1;

知识点

计算 a , b 两个数字是否奇偶性是否相同，可以使用 (a ^ b) & 1 ， 异或操作将处理a , b 两个数字的最后一位是相同（0）还是不同（1）。如果不同（即 num & 1 是否等于 1）则奇偶性不同。

得到前缀和数组之后，遍历 queries 求取每一个子数组范围内，是否是特殊数组即可。 当前缀后与其子数组长度一致时，则改子数组是特殊数组。

代码如下：

TypeScript

function isArraySpecial(nums: number[], queries: number[][]): boolean[] {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if ((nums[i] ^ nums[i-1]) & 1) {
            dp[i] = dp[i - 1] + 1;
        }
    }
    const ans = [];
    for (const [x, y] of queries) {
        ans.push((dp[y] - dp[x]) >= y - x); // dp[y] >= y - x + 1
    }
    return ans;
};

Footnotes

1. 子数组 是数组中元素的连续序列。 ↩