3152：特殊数组 II（1523 分）

力扣第 398 场周赛第 2 题

题目

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

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

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

示例 1：

示例 2：

提示：

• 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
2
3
4
5
6
7

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        res,w = [1],1
        for a,b in pairwise(nums):
            w = w+1 if (a+b)%2 else 1
            res.append(w)
        return [res[b]>b-a for a,b in queries]

100 ms