题目描述:
如果数组的每一对相邻元素都是两个奇偶性不同的数字,则该数组被认为是一个 特殊数组 。
你有一个整数数组 nums
和一个二维整数矩阵 queries
,对于 queries[i] = [fromi, toi]
,请你帮助你检查
子数组
nums[fromi..toi]
是不是一个 特殊数组 。
返回布尔数组 answer
,如果 nums[fromi..toi]
是特殊数组,则 answer[i]
为 true
,否则,answer[i]
为 false
输入输出实例:
思路:这道题目乍一看和昨天的题目差不多就只是多了一道遍历queries数组的过程,但是由于时间复杂度比较高最后会有一个实例过不了,所以我们需要改变一下思路。
使用比较直接的方法(时间复杂度高):
class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:ans = []for from_i,to_i in queries:flag = 1for i in range(from_i,to_i):if nums[i]%2==0 and nums[i+1]%2==0:flag = 0breakif nums[i]%2!=0 and nums[i+1]%2!=0:flag = 0breakans.append(True if flag==1 else False)return ans
另一种思路:queries中每一个列表元素中有fromi和toi两个元素,也就是nums数组的fromi下标一直到toi下标,我们可以新建一个列表dp用来存储toi下标之前到toi 有多少个满足特殊数组条件的元素,【比如:nums=[1,2,3,4,2],dp[3] = 4,就是在nums[3]及其之前有连续的四个元素满足特殊数组条件,而dp[4] =1,在nums[4]及其之前只有一个元素满足特殊数组】,所以我们初始化dp值都为1,然后我们比较dp[toi]的值 和 fromi与toi之间的距离,如果是dp[toi]的值更大或者等于fromi与toi之间的距离,那nums[fromi]到nums[toi]这个子数组就肯定是特殊数组。根据上述思路有以下代码:
class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:#dp[i]=n表示 包含nums[i]在内及之前这n个元素满足特殊数组,我们只需要比较toi及之前满足条件的数组长度 与fromi到toi的长度dp = [1] * len(nums)ans = []for i in range(0,len(nums)-1):if (nums[i]%2==0 and nums[i+1]%2!=0) or (nums[i]%2!=0 and nums[i+1]%2==0) :dp[i+1] = dp[i] + 1for from_i,to_i in queries:#如果在nums中在toi及之前的满足特殊数组条件的子数组长度比fromi到toi之间的长度长,那就为Trueans.append(True if dp[to_i] >= to_i - from_i + 1 else False)return ans