https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array/description/
2369. Check if There is a Valid Partition For The Array
給你一個陣列nums，求出是否可以把該陣列切成若干個子陣列，這些陣列需要滿足至少
一個下列的三個條件：
1.子陣列大小為2且元素相同，例如：[2,2]
2.子陣列大小為3且元素相同，例如：[2,2,2]
3.子陣列大小為3，滿足相差為1且遞增，例如：[1,2,3]
Example 1:
Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and
[4,5,6].
This partition is valid, so we return true.
Example 2:
Input: nums = [1,1,1,2]
Output: false
Explanation: There is no valid partition for this array.
思路：
1.用動態規劃，每次要切分 i 之前都去檢查 i - 2 或 i - 3 前面的陣列是否存在
合法的切法。
2.最後返回 dp[n] 即可。
Java Code：
-----------------------------------------------------------
class Solution {
public boolean validPartition(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 2; i <= n; i++) {
if (nums[i - 1] == nums[i - 2]) {
dp[i] = dp[i - 2];
}
if (i >= 3) {
if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]
||
nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] -
nums[i - 3] == 1) {
dp[i] = dp[i] || dp[i - 3];
}
}
}
return dp[n];
}
}
-----------------------------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1691905409.A.F1D.html