网站怎样设计网址,网站建设分辨率,顺口大气三个字公司名字,集团网站建设招标题目链接 Leetcode.2369 检查数组是否存在有效划分 rating : 1780 题目描述
给你一个下标从 0 0 0 开始的整数数组 n u m s nums nums #xff0c;你必须将数组划分为一个或多个 连续 子数组。
如果获得的这些子数组中每个都能满足下述条件 之一 #xff0c;则可以称其为…题目链接 Leetcode.2369 检查数组是否存在有效划分 rating : 1780 题目描述
给你一个下标从 0 0 0 开始的整数数组 n u m s nums nums 你必须将数组划分为一个或多个 连续 子数组。
如果获得的这些子数组中每个都能满足下述条件 之一 则可以称其为数组的一种 有效 划分
子数组 恰 由 2 2 2 个相等元素组成例如子数组 [ 2 , 2 ] [2,2] [2,2] 。子数组 恰 由 3 3 3 个相等元素组成例如子数组 [ 4 , 4 , 4 ] [4,4,4] [4,4,4] 。子数组 恰 由 3 3 3 个连续递增元素组成并且相邻元素之间的差值为 1 1 1 。例如子数组 [ 3 , 4 , 5 ] [3,4,5] [3,4,5] 但是子数组 [ 1 , 3 , 5 ] [1,3,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 ≤ n u m s . l e n g t h ≤ 1 0 5 2 \leq nums.length \leq 10^5 2≤nums.length≤105 1 ≤ n u m s [ i ] ≤ 1 0 6 1 \leq nums[i] \leq 10^6 1≤nums[i]≤106
解法dp
我们定义 f ( i ) f(i) f(i) 考虑 n u m s nums nums 中的前 i i i 个数是否存在有效划分。根据定义 n u m s nums nums 有 n n n 个元素那么 f ( n ) f(n) f(n) 就是最终要返回的答案。
我们直接考虑前 i i i 个数
如果 i ≥ 2 i \geq 2 i≥2 并且 n u m s [ i ] n u m s [ i − 1 ] nums[i] nums[i - 1] nums[i]nums[i−1]那么 f [ i ] f [ i − 2 ] f[i] f[i - 2] f[i]f[i−2]如果 i ≥ 3 i \geq 3 i≥3
如果 n u m s [ i − 2 ] n u m s [ i − 1 ] a n d n u m s [ i − 1 ] n u m s [ i ] nums[i-2]nums[i-1]\ and\ nums[i-1]nums[i] nums[i−2]nums[i−1] and nums[i−1]nums[i]那么 f [ i ] f [ i − 3 ] f[i] f[i - 3] f[i]f[i−3]如果 n u m s [ i − 2 ] 1 n u m s [ i − 1 ] a n d n u m s [ i − 1 ] 1 n u m s [ i ] nums[i-2]1nums[i-1]\ and\ nums[i-1]1nums[i] nums[i−2]1nums[i−1] and nums[i−1]1nums[i]那么 f [ i ] f [ i − 3 ] f[i] f[i - 3] f[i]f[i−3]
只要上述三种情况有一个为真那么 f [ i ] f[i] f[i] 就为真
初始时 f [ 0 ] t r u e f[0] true f[0]true即没有元素也是一种有效划分
注意 f [ 1 ] f[1] f[1] 表示第一个元素而 n u m s [ 0 ] nums[0] nums[0] 表示第一个元素。所以关于 n u m s nums nums 下标都要减 1 1 1
最终
如果 i ≥ 2 i \geq 2 i≥2 并且 n u m s [ i − 1 ] n u m s [ i − 2 ] nums[i - 1] nums[i - 2] nums[i−1]nums[i−2]那么 f [ i ] f [ i − 2 ] f[i] f[i - 2] f[i]f[i−2]如果 i ≥ 3 i \geq 3 i≥3
如果 n u m s [ i − 3 ] n u m s [ i − 2 ] a n d n u m s [ i − 2 ] n u m s [ i − 1 ] nums[i-3]nums[i-2]\ and\ nums[i-2]nums[i-1] nums[i−3]nums[i−2] and nums[i−2]nums[i−1]那么 f [ i ] f [ i − 3 ] f[i] f[i - 3] f[i]f[i−3]如果 n u m s [ i − 3 ] 1 n u m s [ i − 2 ] a n d n u m s [ i − 2 ] 1 n u m s [ i − 1 ] nums[i-3]1nums[i-2]\ and\ nums[i-2]1nums[i-1] nums[i−3]1nums[i−2] and nums[i−2]1nums[i−1]那么 f [ i ] f [ i − 3 ] f[i] f[i - 3] f[i]f[i−3]
时间复杂度 O ( n ) O(n) O(n)
C代码
class Solution {
public:bool validPartition(vectorint nums) {int n nums.size();vectorint f(n 1);f[0] 1;for(int i 2;i n;i){if(nums[i - 1] nums[i - 2]) f[i] | f[i - 2];if(i 3){if(nums[i - 1] nums[i - 2] nums[i - 2] nums[i - 3]) f[i] | f[i - 3];if(nums[i - 3] 1 nums[i - 2] nums[i - 2] 1 nums[i - 1]) f[i] | f[i - 3];}}return f[n];}
};
