LeetCode每日一题(2369. Check if There is a Valid Partition For The Array)

You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.

We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:

The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.
Return true if the array has at least one valid partition. Otherwise, return false.

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.

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106

---

假设 dp[i]为以 nums[i]为起点的结果, 那么我们需要检查以下几种情况:

• 如果 nums[i] == nums[i+1] == nums[i+2], 此时如果 dp[i+3]为 true, 则整体结果为 true
• 如果 nums[i] == nums[i+1], 此时如果 dp[i+2]为 true, 则整体结果为 true
• 如果 nums[i+2] - nums[i+1] == 1 并且 nums[i+1] - nums[i] == 1, 此时如果 dp[i+3]为 true， 则整体结果为 true

注意考虑 nums[i]之后的元素不足 3 个的情况

---

use std::collections::HashMap;

impl Solution {
    fn dp(nums: &Vec<i32>, i: usize, cache: &mut HashMap<usize, bool>) -> bool {
        let length = nums.len();
        if i == length {
            return true;
        }
        if i == length - 1 {
            return false;
        }
        if i == length - 2 {
            return nums[length - 1] == nums[length - 2];
        }
        if nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2] {
            let next = if let Some(c) = cache.get(&(i + 3)) {
                *c
            } else {
                Solution::dp(nums, i + 3, cache)
            };
            if next {
                return true;
            }
        }
        if nums[i] == nums[i + 1] {
            let next = if let Some(c) = cache.get(&(i + 2)) {
                *c
            } else {
                Solution::dp(nums, i + 2, cache)
            };
            if next {
                return true;
            }
        }
        if nums[i + 2] - nums[i + 1] == 1 && nums[i + 1] - nums[i] == 1 {
            let next = if let Some(c) = cache.get(&(i + 3)) {
                *c
            } else {
                Solution::dp(nums, i + 3, cache)
            };
            if next {
                return true;
            }
        }
        cache.insert(i, false);
        false
    }
    pub fn valid_partition(nums: Vec<i32>) -> bool {
        Solution::dp(&nums, 0, &mut HashMap::new())
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51