湘潭网站建设厦门网站制作,迁移wordpress 500,淘宝网站开发实训报告,网站内容批量替换一、题目
1、题目描述 给你一个下标从 0 开始的整数数组 nums #xff0c;你必须将数组划分为一个或多个 连续 子数组。 如果获得的这些子数组中每个都能满足下述条件 之一 #xff0c;则可以称其为数组的一种 有效 划分#xff1a; 子数组 恰 由 2 个相等元素组成#xf…一、题目
1、题目描述 给你一个下标从 0 开始的整数数组 nums 你必须将数组划分为一个或多个 连续 子数组。 如果获得的这些子数组中每个都能满足下述条件 之一 则可以称其为数组的一种 有效 划分 子数组 恰 由 2 个相等元素组成例如子数组 [2,2] 。子数组 恰 由 3 个相等元素组成例如子数组 [4,4,4] 。子数组 恰 由 3 个连续递增元素组成并且相邻元素之间的差值为 1 。例如子数组 [3,4,5] 但是子数组 [1,3,5] 不符合要求。 如果数组 至少 存在一种有效划分返回 true 否则返回 false 。 2、接口描述
class Solution {
public:bool validPartition(vectorint nums) {}
}; 3、原题链接
2369. 检查数组是否存在有效划分 二、解题报告
1、思路分析
属于入门级别的动态规划问题
定义状态f[i]为前i个元素是否存在有效划分
那么根据划分的定义第i个元素可以和它左边的两个元素以及左边相邻的一个元素进行状态转移
三种划分定义可以有三个状态转移方程
代码还是很好写的注意初始化以及状态转移不要越界
2、复杂度 时间复杂度 O(N)空间复杂度O(N) 3、代码详解
class Solution {
public:
bool f[100005];bool validPartition(vectorint nums) {memset(f, 0, sizeof f), f[0] 1, f[2] nums[0] nums[1];int n nums.size();for(int i 3, x; i n; i){if(nums[i - 1] nums[i - 2]) f[i] f[i] || f[i - 2];if(nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3])f[i] f[i] || f[i - 3];if(nums[i - 1] - 1 nums[i - 2] nums[i - 2] - 1 nums[i - 3])f[i] f[i] || f[i - 3];}return f[n];}
};
