【LC3152】特殊数组 II
Little_YangYang

题干

如果数组的每一对相邻元素都是两个奇偶性不同的数字,则该数组被认为是一个 特殊数组 。 你有一个整数数组 nums 和一个二维整数矩阵 queries,对于 queries[i] = [fromi, toi],请你帮助你检查 子数组 nums[fromi..toi] 是不是一个 特殊数组 。 返回布尔数组 answer,如果 nums[fromi..toi] 是特殊数组,则 answer[i] 为 true ,否则,answer[i] 为 false 。

思路

根据题意,如果某一个数与前一个数字特殊数组,我们可以使用位运算简单判别,即

1
(nums[i-1] ^ nums[i]) & 1

我们维护一个前缀和数组,如果数字与数字构成特殊数组,则将其置为,否则就将其置为

显然,如果查询区间符合特殊数组的规则,则有

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isArraySpecial(nums []int, queries [][]int) []bool {
sum := make([]int, len(nums))
for i := 1; i < len(nums); i++ {
sum[i] = sum[i-1]
if (nums[i-1]^nums[i])&1 == 0 {
sum[i]++
}
}
ans := make([]bool, len(queries))
for i, r := range queries {
ans[i] = sum[r[0]] == sum[r[1]]
}
return ans
}