3152. Special Array II
Problem
An array is considered special if every pair of its adjacent elements contains two numbers with different parity.
You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromᵢ, toᵢ] your task is to check that subarray nums[fromᵢ..toᵢ] is special or not.
A subarray is a contiguous sequence of elements within an array.
Return an array of booleans answer such that answer[i] is true if nums[fromᵢ..toᵢ] is special.
https://leetcode.com/problems/special-array-ii/
Example 1:
Input:
nums = [3,4,1,2,6], queries = [[0,4]]
Output:[false]
Explanation:
The subarray is[3,4,1,2,6]. 2 and 6 are both even.
Example 2:
Input:
nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output:[false,true]
Explanation:
- The subarray is
[4,3,1]. 3 and 1 are both odd. So the answer to this query is false.- The subarray is
[1,6]. There is only one pair:(1,6)and it contains numbers with different parity. So the answer to this query is true.
Constraints:
1 <= nums.length <= 10⁵1 <= nums[i] <= 10⁵1 <= queries.length <= 10⁵queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1
Test Cases
class Solution:
def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:import pytest
from solution import Solution
@pytest.mark.parametrize('nums, queries, expected', [
([3,4,1,2,6], [[0,4]], [False]),
([4,3,1,6], [[0,2],[2,3]], [False,True]),
([3,4,1,2,6], [[3,4]], [False]),
])
class Test:
def test_solution(self, nums, queries, expected):
sol = Solution()
assert sol.isArraySpecial(nums, queries) == expected
Thoughts
3151. Special Array I 的进阶版,从一次查询增加成 q 次查询。
跟 3258. Count Substrings That Satisfy K-Constraint I 到 3261. Count Substrings That Satisfy K-Constraint II 进阶类似。
直接算是 O(n²) 时间,因为不同的 query 之间可能有大量重复的判定。这种情况很适合动态规划。
令 dp(i) 表示以 nums[i] 为终点的最长连续奇偶交替的 subarray 长度。显然:
这样对于任意 query (from, to),比较 query 区间的长度 to - from + 1 和 dp(to) 的大小,如果前者 小于等于 后者(to - from + 1 <= dp(to) ⟺ from > to - dp(to))则为 true,否则是 false。
时间复杂度 O(n),空间复杂度 O(n)。
Code
class Solution:
def isArraySpecial(self, nums: list[int], queries: list[list[int]]) -> list[bool]:
n = len(nums)
dp = [1] * n
prev = nums[0] & 1
for i in range(1, n):
if prev != (prev := nums[i] & 1):
dp[i] += dp[i - 1]
return [f > t - dp[t] for f, t in queries]
评论需要 JavaScript。