力扣 3152. 特殊数字Ⅱ

题目描述

queries二维数组是nums数组待判断的索引区间（左闭右闭）。需要判断每个索引区间中的nums相邻元素奇偶性是否不同，如果都不同则该索引区间的搜索结果为True，否则为False。

暴力推演：也是我最开始的思路

遍历queries的索引区间，在每一个区间内再遍历相应的nums元素判断奇偶性是否不同。
那么，如何判断相邻元素的奇偶性不同呢？我想到的是：“奇数+偶数=奇数”而“奇数+奇数=偶数”、“偶数+偶数=偶数”，即判断相邻元素之和是否为奇数。

该思路代码如下：

class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:# 相邻数字奇偶性不同：和为奇数。# 暴力搜索：遍历数组的每一个查询索引区间，依次判断。# 时间复杂度：O(M*N)，其中M为queries的长度，N为nums的长度。answer = []for index_range in queries:result = True  # 首先假设区间符合要求for i in range(index_range[0], index_range[1]): if (nums[i] + nums[i + 1]) % 2 == 0:  # 检查和是否为偶数result = False  # 找到一对不符合要求的相邻数字break  # 找到后立即停止循环answer.append(result)return answer

这个思路时间复杂度过高。该如何优化呢？
我们发现这个思路再遍历queries每个区间时都要在nums中进行从头到尾的遍历，这一部分是不是可以优化呢？
比如可以先遍历nums中所有的元素，判断相邻元素奇偶性差异并在相应的位置做好标记，如果该位置与前一个元素的奇偶性不同，则该位置的标记与前一个位置的标记保持一致，否则＋1，这样的话每次只需要判断区间首位位置的标记是否相同即可（时间复杂度即可变为O（M+N），如果相同则说明该区间所有的相邻元素奇偶性都不同，输出True，否则输出False。
看了题解，原来这个标记的思路其实可以用前缀和（之前很少用到，练练）来实现，而且判断两个元素奇偶性差异可以直接用位运算（也很少用到，正好练练）。

前缀和

前缀和是什么呢？
前缀和是一种在数组或序列中计算元素累积和的方法。具体来说，对于一个数组或序列中的元素，前缀和是指从第一个元素到当前元素（包括当前元素）的所有元素的和。

位运算是什么？
位运算是一种直接对整数的二进制位进行操作的运算方式。在计算机科学中，位运算是一种非常基础且高效的运算方式，它在底层硬件和编程语言中广泛使用。位运算主要包括以下几种类型：
1、AND（与）运算：符号为 &。两个位相与，只有两个位都是1时结果才是1，否则是0。
2、OR（或）运算：符号为 |。两个位相或，只要有一个位是1结果就是1，否则是0。
3、XOR（异或）运算：符号为 ^。两个位相异或，相同则结果为0，不同则结果为1。
4、NOT（非）运算：符号为 ~。对一个位取反，1变成0，0变成1。
5、左移（Left Shift）运算：符号为 <<。将一个数的所有位向左移动指定的位数，左边超出的位被丢弃，右边空出的位补0。
6、右移（Right Shift）运算：符号为 >>。将一个数的所有位向右移动指定的位数，右边超出的位被丢弃，左边空出的位补原数的符号位（算术右移）或补0（逻辑右移）。

位运算如何判断两个元素奇偶性差异？
对照上面的位运算类型，用异或！！
nums[i-1] ^ nums[i] == 1即为相邻元素奇偶性不同。

该思路代码如下：

class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:# 前缀和：在数组或序列中计算元素累积和的方法，具体来说是指从第一个元素到当前元素（包括当前元素）的所有元素的和。# 快速计算某个范围内的元素总和的场景，可以帮助简化问题，提高算法效率。# 时间复杂度：O(M+N)n = len(nums)sum_array = [0] * nfor i in range(1, n):sum_array[i] = sum_array[i-1]if ((nums[i-1] ^ nums[i]) & 1) == 0: # 位运算判断，如果奇偶性相同条件则为真sum_array[i] += 1m = len(queries)answer = [False] * mfor i in range(m):index_range = queries[i]if sum_array[index_range[0]] == sum_array[index_range[1]]:  #若区间两端的标记一致，则说明区间内的相邻元素均满足奇偶性不同的条件。answer[i] = Truereturn answer

我试了试把位运算判断的条件改成：

if nums[i-1] ^ nums[i] == 0:

测试用例报错：

我觉得这两句效果一样，但输出结果就是不一样，也不知道为啥。。。留待后续！！

后续

用位运算判断两数的奇偶性差异：看二进制最后一位是否相同。而 nums[i-1] ^ nums[i] 会比较每一位是否相同，所以要 (nums[i-1] ^ nums[i]) & 1 ，因为只关注异或运算的最低位结果。

参考题解： 【预处理】前缀和 & 动态规划（详细思路+推导）