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
题解:
1、尝试使用递推,出现运行超时。
2、使用动态规划解决。
code:
递推,超出时间限制
class Solution {
public boolean validPartition(int[] nums) {
return isValid(nums, 0);
}
boolean isValid(int[] nums, int start) {
if (start == nums.length) {
return true;
}
int n = nums.length;
boolean check = false;
if (start + 1 < n) {
if (nums[start] == nums[start + 1]) {
check = check || isValid(nums, start + 2);
}
}
if (start + 2 < n) {
if (nums[start] == nums[start + 1] && nums[start + 1] == nums[start + 2]) {
check = check || isValid(nums, start + 3);
}
if ((nums[start + 1] - nums[start] == 1)&& (nums[start + 2] - nums[start + 1] == 1)) {
check = check || isValid(nums, start + 3);
}
}
return check;
}
}
dp
class Solution {
public boolean validPartition(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
if (i >= 2) {
dp[i] = dp[i - 2] && validTwo(nums[i - 2], nums[i - 1]);
}
if (i >= 3) {
dp[i] = dp[i] || (dp[i - 3] && validThree(nums[i - 3], nums[i - 2], nums[i - 1]));
}
}
return dp[n];
}
public boolean validTwo(int num1, int num2) {
return num1 == num2;
}
public boolean validThree(int num1, int num2, int num3) {
return (num1 == num2 && num1 == num3) || (num1 + 1 == num2 && num2 + 1 == num3);
}
}
原文地址:https://blog.csdn.net/xiao__jia__jia/article/details/136392973
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!