特殊数组Ⅱ。用go语言，一个数组被称为“特殊数组”，如果它的每一对相邻元素的奇偶性不同。给定一个整数数组 nums 和一个二维整数矩阵 queries，我们需要判断对于每一个查询 queries[i] = [fromi, toi]，对应的子数组 nums[fromi..toi] 是否为特殊数组。
最终，我们将返回一个布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true；否则为 false。
1 <= nums.length <= 100000。
1 <= nums[i] <= 100000。
1 <= queries.length <= 100000。
queries[i].length == 2。
0 <= queries[i][0] <= queries[i][1] <= nums.length - 1。
输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]。
输出：[false,true]。
解释：
子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。
大体步骤如下：
1.首先通过函数isArraySpecial来判断数组中每一对相邻元素的奇偶性是否不同，以确定是否为特殊数组。
2.初始化一个长度为n的数组dp，用于存储到当前位置为止，符合条件的最长连续子数组长度。
3.从第二个元素开始遍历数组nums，如果当前元素和前一个元素的异或结果的奇偶性不同，则更新dp[i]为dp[i-1]+1，表示连续特殊的子数组长度增加了。
4.对于每一个查询queries[i]，取出起始位置x和结束位置y，判断dp[y]是否大于等于区间长度y-x+1，如果是，则当前子数组符合特殊数组要求，对应结果为true；否则为false。
5.将每个查询的结果存储在布尔数组res中，并返回该数组作为输出。
总的时间复杂度：
- 对数组
nums的遍历需要O(n)的时间复杂度，其中n为数组的长度。 - 对查询二维矩阵
queries的遍历需要O(q)的时间复杂度，其中q为查询矩阵的长度。 - 因此，总的时间复杂度为
O(n + q)。
总的额外空间复杂度：
- 除了存储输入数量级的空间外，额外使用了长度为
n的数组dp和长度为q的结果数组，因此额外空间复杂度为O(n + q)。
Go完整代码如下：
package main
import (
"fmt"
)
func isArraySpecial(nums []int, queries [][]int) []bool {
n := len(nums)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}
for i := 1; i < n; i++ {
if (nums[i]^nums[i-1])&1 == 1 {
dp[i] = dp[i-1] + 1
}
}
res := make([]bool, len(queries))
for i, q := range queries {
x, y := q[0], q[1]
res[i] = dp[y] >= y-x+1
}
return res
}
func main() {
nums := []int{4, 3, 1, 6}
queries := [][]int{{0, 2}, {2, 3}}
fmt.Println(isArraySpecial(nums, queries))
}
Rust完整代码如下：
fn is_array_special(nums: &Vec<i32>, queries: &Vec<Vec<i32>>) -> Vec<bool> {
let n = nums.len();
let mut dp = vec![1; n];
for i in 1..n {
if (nums[i] ^ nums[i - 1]) & 1 == 1 {
dp[i] = dp[i - 1] + 1;
}
}
let mut res = vec![false; queries.len()];
for (i, q) in queries.iter().enumerate() {
let x = q[0] as usize;
let y = q[1] as usize;
res[i] = dp[y] >= (y - x + 1);
}
res
}
fn main() {
let nums = vec![4, 3, 1, 6];
let queries = vec![vec![0, 2], vec![2, 3]];
println!("{:?}", is_array_special(&nums, &queries));
}
