【Leetcode】2369. 检查数组是否存在有效划分

文章目录

题目
思路
代码
结果

题目

题目链接
给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个连续子数组。

如果获得的这些子数组中每个都能满足下述条件之一，则可以称其为数组的一种有效划分：

子数组恰由 2 个相等元素组成，例如，子数组 [2,2] 。
子数组恰由 3 个相等元素组成，例如，子数组 [4,4,4] 。
子数组恰由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
如果数组至少存在一种有效划分，返回 true ，否则，返回 false 。

示例 1：
输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。

示例 2：
输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

提示：
2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

思路

这道题可以使用动态规划来进行解答。

通过前面（n-2）个元素或者是前面（n-3）个元素来进行判断整个数组是否存在有效的划分。如果前面（n-2）个元素存在有效的划分，并且最后两个元素是相等的，那么整个数组就存在有效的划分。亦或是前面的（n-3）个元素存在有效的划分，最后三个元素相等或者是满足3个连续递增元素的要求，数组也可以说明存在有效的划分。
上面就是动态规划的基本思路，创建一个长度为（n+1）的数组 dp 来记录数组 nums 是否存在一个有效的划分，其中 dp[i] 表示前面 i 个元素所组成的数组是否存在一个可行的划分。最终计算出来的 dp[n] 就是结果

代码

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        if (n == 2) {
            return nums[1] == nums[0];
        }
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[2] = nums[1] == nums[0];
        for (int i = 3; i < n + 1; ++i) {
            if (nums[i - 1] == nums[i - 2]) {
                dp[i] |= dp[i - 2];
            }
            if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {
                dp[i] |= dp[i - 3];
            }
            if (nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1) {
                dp[i] |= dp[i - 3];
            }
        }
        return dp[n];
    }
};