leetcode 3152. 特殊数组 II

zhaojun

2024 年 08 月 13 日

313 次浏览

暂无评论

1540字数

默认分类

https://leetcode.cn/problems/special-array-ii/description/

## 题目

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 **特殊数组** 。

你有一个整数数组 `nums` 和一个二维整数矩阵 `queries`，对于 `queries[i] = [fromi, toi]`，请你帮助你检查子数组 `nums[fromi..toi]` 是不是一个 **特殊数组** 。

返回布尔数组 `answer`，如果 $nums[from_i..to_i]$ 是特殊数组，则 `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]
**解释：**
1. 子数组是 `[4,3,1]`。3 和 1 都是奇数。因此这个查询的答案是 `false`。
2. 子数组是 `[1,6]`。只有一对：`(1,6)`，且包含了奇偶性不同的数字。因此这个查询的答案是 `true`。

## 思路

首先，如果一个区间是特殊数组，那它的任意子区间也一定是特殊数组。

那么我们可以记录 `nums` 中每个下标的最大特殊数组长度，如:

```
[3,4,1,2,6,1,3] nums
[1,2,3,4,1,2,1] dp
```

如 `dp[5]` 为 `2`，表示 `dp[4 - 5]` 是特殊数组, 那么对于区间 `[i, j]`，只要判断 `dp[j]` 的值(以该下标为结尾的最长特殊数组长度)大于等于当前区间长度 `j - i + 1` 就表示包含了该区间，就肯定是特殊数组。

## 代码
```java
class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] % 2 != nums[i - 1] % 2) {
                dp[i] = dp[i - 1] + 1;
            }
        }

boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0], y = queries[i][1];
            res[i] = dp[y] >= y - x + 1;
        }

return res;
    }
}
```

最后修改：2024 年 10 月 08 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 3152. 特殊数组 II

zhaojun • 2024 年 08 月 13 日

leetcode 3152. 特殊数组 II

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

Git 笔记

leetcode 1247. 交换字符使得字符串相同

leetcode 3152. 特殊数组 II

使用 Gost 来实现 sniproxy

1. MySQL 主从搭建 —— 基础篇

leetcode 3152. 特殊数组 II

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 3152. 特殊数组 II

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款