↓Skip to main content
  1. Posts/

LeetCode-3152 特殊数组 II

·1 min·
Table of Contents

LeetCode-3152 特殊数组 II #

Solution 1 #

把奇数下标的元素都减去 $1$, 那么原数组中相邻元素奇偶性不同的子数组就变成了现在奇偶性全部相同的子数组. 用前缀和来判断.

代码如下:

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        for i in range(len(nums)):
            if i & 1:
                nums[i] -= 1
            nums[i] = 1 if nums[i] & 1 else 0
        presum = list(accumulate(nums, initial=0))
        return [presum[r + 1] - presum[l] in [0, r - l + 1] for l, r in queries]

Solution 2 #

定义 $$ a[i] = \begin{cases} 0, nums[i]%2\equiv nums[i + 1]\mod2 \ 1, nums[i]%2 \not\equiv nums[i + 1]\mod2 \end{cases} $$ 那么对于一个查询 $[l,r]$ , 查看 $a[l], \dots,a[r - 1]$ 中是否全部为 $0$ 即可.

代码如下:

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        s = list(accumulate((x & 1 == y & 1 for x, y in pairwise(nums)), initial=0))
        return [s[l] == s[r] for l, r in queries]