2024-12-25：特殊数组Ⅱ。用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。

答案2024-12-25：

chatgpt

题目来自leetcode3152。

大体步骤如下：

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));
}