手机端网站建站流程,汾湖做网站,网站添加什么东西才能和用户体验,如何做 旅游网站内容2369. 检查数组是否存在有效划分
给你一个下标从 0 开始的整数数组 nums #xff0c;你必须将数组划分为一个或多个 连续 子数组。
如果获得的这些子数组中每个都能满足下述条件 之一 #xff0c;则可以称其为数组的一种 有效 划分#xff1a;
子数组 恰 由 2 个相等元素…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 105 1 nums[i] 106 题解
本题把握好状态定义即可 因像本题有连续字眼 使用DP相对更加宏观 从大问题分解为小问题着手: ⭐我们先确定好边界情况即不妨枚举几个小数字看看 1.如果只有一张牌 则必定无法划分; 2.如果只有两张牌 则若相等则可以划分 不等则无法划分; 3.如果只有三张牌 则若前两张牌相等且第三张和前两张同则可划分 或者三张牌为顺子也可划分 不符前二者则无法划分; 因此当有四张牌时对于第四张新加入的牌由于为连续划分则第四张必定是要和前面相邻的若干张去组成而前面三张的各个情况已经确定故我们对新加入的第四张导致的所有可能划分做出枚举判断即可。 ⭐因此当四张牌时若可以划分则为以下几种情况成立: 1. 前4-2张为可划分 且3、4张可组成两相等元素形式 2. 前4-3张为可划分 且2、3、4 张可组成三相等元素形式 3. 前4-3张为可划分 且2、3、4 张可组成顺子形式 其余情况则均为不可划分。 因此推广到n,不妨定义dp[i]为从0到下标i所有元素组成的划分情况: ⭐dp[i] 1 代表0到i张牌 均为可划分 ⭐dp[i] -1 代表0到i张牌 为不可划分 因此对每次加入的nums[i]这张新牌判断通过其和前1张或2张组成的情况及dp[i-2] dp[i-3]是否为可划分来判断dp[i] 是否为可划分 代码
class Solution {public boolean validPartition(int[] nums) {/* 本题把握好状态定义即可 因像本题有连续字眼 使用DP相对更加宏观 从大问题分解为小问题着手:我们先确定好边界情况即不妨枚举几个小数字看看因此如果只有一张牌 则必定无法划分;如果只有两张牌 则若相等则可以划分 不等则无法划分;如果只有三张牌 则若前两张牌相等且第三张和前两张同则可划分 或者三张牌为顺子也可划分 不符前二者则无法划分;因此当有四张牌时对于第四张新加入的牌由于为连续划分则第四张必定是要和前面相邻的若干张去组成而前面三张的各个情况已经确定故我们对新加入的第四张导致的所有可能划分做出枚举判断即可。因此当四张牌时若可以划分则为以下几种情况成立:1. 前4-2张为可划分 且3、4张可组成两相等元素形式2. 前4-3张为可划分 且2、3、4 张可组成三相等元素形式3. 前4-3张为可划分 且2、3、4 张可组成顺子形式其余情况则均为不可划分。因此推广到n,不妨定义dp[i]为从0到下标i所有元素组成的划分情况:dp[i] 1 代表0到i张牌 均为可划分dp[i] -1 代表0到i张牌 为不可划分因此对每次加入的nums[i]这张新牌判断通过其和前1张或2张组成的情况及dp[i-2] dp[i-3]是否为可划分来判断dp[i] 是否为可划分⭐*/int len nums.length;int dp[] new int[len];dp[0] -1;if(nums[0] nums[1])dp[1] 1;elsedp[1] -1;if(len 2)return dp[1] 1 ? true : false;if(dp[1] 1 nums[2] nums[1])dp[2] 1;else if(check(nums[0],nums[1],nums[2]))dp[2] 1;elsedp[2] -1;if(len 3)return dp[2] 1 ? true : false;for(int i3;ilen;i){if(dp[i-2] 1 nums[i-1] nums[i]){dp[i] 1;}else if(dp[i-3] 1 nums[i-1] nums[i] nums[i-2] nums[i-1]){dp[i] 1;}else if(dp[i-3] 1 check(nums[i-2],nums[i-1],nums[i])){dp[i] 1;}else{dp[i] -1;}}return dp[len-1] 1 ? true : false;}public boolean check(int n1,int n2,int n3){if(n3 - n2 1 n2 - n1 1)return true;return false;}
}结果
