LC.P2369[检查数组是否存在有效划分]

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int[] nums;
    int n;
    Boolean[] f;

    public boolean validPartition(int[] nums) {
        this.nums = nums;
        n = nums.length;
        f = new Boolean[n];
        return dfs(0);
    }

    private boolean dfs(int i) {
        if (i == n) return true;
        if (f[i] != null) return f[i];
        boolean a = i + 1 < n && nums[i] == nums[i + 1];
        boolean b = i + 2 < n && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2];
        boolean c = i + 2 < n && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1;
        return f[i] = ((a && dfs(i + 2)) || ((b || c) && dfs(i + 3)));
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for (int i = 1; i <= n; ++i) {
            boolean a = i - 2 >= 0 && nums[i - 1] == nums[i - 2];
            boolean b = i - 3 >= 0 && nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3];
            boolean c = i - 3 >= 0 && nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1;
            f[i] = (a && f[i - 2]) || ((b || c) && f[i - 3]);
        }
        return f[n];
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$