题干描述
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
你有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助你检查
子数组
nums[fromi..toi] 是不是一个 特殊数组 。
返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。
示例 1：
输入：nums = [3,4,1,2,6], queries = [[0,4]]
输出：[false]
解释：
子数组是 [3,4,1,2,6]。2 和 6 都是偶数。
示例 2：
输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
输出：[false,true]
解释：
- 子数组是
[4,3,1]。3 和 1 都是奇数。因此这个查询的答案是false。 - 子数组是
[1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是true。
题干分析
题目还要求我们判断一个给定的子数组是否为“特殊数组”。特殊数组的定义是：数组中的每一对相邻元素奇偶性都不同。换句话说，数组中的每一对相邻元素，一个是奇数，两一个是偶数。
这个算法的核心是利用动态规划思想，计算以每个元素结尾的最长特殊子数组的长度，然后根据查询检查每个子数组是否为“特殊数组”。
1.动态规划数组dp的构建
- dp[i]表示以nums[i]结尾的最长特殊数组的长度。
- 初始化时，所有元素的dp[i]都被设为1，因为单个元素本身是一个长度为1的“特殊数组”。
- 然后从第二个元素开始遍历数组nums，遍历nums[i]与nums[i-1]的奇偶性不同，则dp[i] = dp[i-1] + 1,表示当前子数组仍然是特殊数组，且长度增加1。
2.查询处理
- 对于每个查询[x,y]，检查dp[y]是否大于或等于y-x+1，也就是检查以nums[y]结尾的特殊数组长度是否足够覆盖整个查询的区间长度。
- 如果dp[y]的长度大于或等于区间[x,y]的长度，则说明该子数组为特殊数组，返回true，否则返回false。
3.时间复杂度
- 预处理dp数组的时间复杂度o（n），其实n师叔祖nums的长度。
- 每个查询的时间复杂度为o（1），因为只需要检查dp数组的值。
- 整个算法的时间复杂度为o（n + q），其中q是查询的数量。
完整代码如下
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//定义一个函数用于判断数组是否为特殊数组
bool* isArraySpecial(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {//动态分配dp数组，用于存储以当前元素结尾的最长特殊数组长度int* dp = (int*)malloc(numsSize * sizeof(int));for (int i = 0; i < numsSize; i++){dp[i] = 1;//初始化dp数组，最小的特殊数组长度为1}//填充dp数组for (int i = 1; i < numsSize; i++){//如果当前元素与前一个原酸的奇偶性不同，则更新dp[i]if ((nums[i] ^ nums[i - 1]) & 1){dp[i] = dp[i - 1] + 1;}}//动态分配结果数组resbool* res = (bool*)malloc(queriesSize * sizeof(bool));for (int i = 0; i < queriesSize; i++){int x = queries[i][0], y = queries[i][1];//检查dp[y]是否大于或等于区间长度，判断是否为特殊数组res[i] = dp[y] >= y - x + 1;}//释放dp数组的内存free(dp);//设置返回数组的大小*returnSize = queriesSize;return res;
}
// 示例使用
int main() {int nums[] = { 1, 2, 3, 4, 5, 6 };int numsSize = sizeof(nums) / sizeof(nums[0]);// 创建查询int queriesSize = 3;int queriesColSize[] = { 2, 2, 2 };int** queries = (int**)malloc(queriesSize * sizeof(int*));queries[0] = (int*)malloc(2 * sizeof(int)); queries[0][0] = 0; queries[0][1] = 2;queries[1] = (int*)malloc(2 * sizeof(int)); queries[1][0] = 1; queries[1][1] = 3;queries[2] = (int*)malloc(2 * sizeof(int)); queries[2][0] = 2; queries[2][1] = 5;// 结果数组大小int returnSize;// 调用函数bool* result = isArraySpecial(nums, numsSize, queries, queriesSize, queriesColSize, &returnSize);// 输出结果for (int i = 0; i < returnSize; i++) {printf("查询 %d: %s\n", i + 1, result[i] ? "true" : "false");}// 释放内存for (int i = 0; i < queriesSize; i++) {free(queries[i]);}free(queries);free(result);return 0;
}
