LeetCode6137 检查数组是否存在有效划分

发表于 | 分类于 |
字数统计: 325 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/

题意

给定一个数组
如果获得的这些子数组中每个都能满足下述条件之一 ，则可以称其为数组的一种有效划分：
子数组由 2 个相等元素组成，例如，子数组 [2,2] 。
子数组由 3 个相等元素组成，例如，子数组 [4,4,4] 。
子数组由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5]

解法

周赛第三题
脑子一下子没转过来 卡了一个多小时
只能想出来dfs
难写还超时
其实只要dp一下就好了
令dp[i]表示以i结尾是否满足条件
然后每次三个条件判断一下是不是满足
最后dp[n]就是答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool validPartition(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n + 1);
    dp[0] = 1;
    dp[2] = (nums[0] == nums[1]);
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i] | (dp[i - 2] && nums[i - 1] == nums[i - 2]);
        dp[i] = dp[i] | (dp[i - 3] && nums[i - 1] == nums[i - 2] 
                                && nums[i - 2] == nums[i - 3]);
        dp[i] = dp[i] | (dp[i - 3] && nums[i - 1] == nums[i - 2] + 1
                                && nums[i - 2] == nums[i - 3] + 1);            
    }
    return dp[n];
}