Leetcode 2750. Ways to Split Array Into Good Subarrays

[Woodyiiiiiii]

2750. Ways to Split Array Into Good Subarrays

2750. Ways to Split Array Into Good Subarrays

类似问题：
930. Binary Subarrays With Sum

1、DP

这道题我又是思维定式直接想到用动态规划来做。

虽然这不是正解，但是可以硬着头皮做下去的。难点在于如何优化，那最多耗时是O(nlgn)，所以最后用二分解决了问题。

class Solution {
   int n;
    int[] nums;
    int[] prefix;
    final int MOD = (int) (1e9 + 7);
    Map<Integer, Long> memo = new HashMap<>();

    public int numberOfGoodSubarraySplits(int[] nums) {
        n = nums.length;
        this.nums = nums;
        prefix = new int[n];
        for (int i = 0; i < n; i ++) {
            prefix[i] = i > 0 ? prefix[i - 1] + nums[i] : nums[i];
        }
        return (int) dfs(0);
    }

    private long dfs(int i) {
        if (i >= n) {
            return 1;
        }
        if (memo.containsKey(i)) {
            return memo.get(i);
        }

        long ans = 0;
        int target = (i > 0 ? prefix[i - 1] : 0) + 1;
        int left = bs1(prefix, i, n, target), right = bs2(prefix, i, n, target);
        int cnt = prefix[n - 1] != target ? right - left + 1 : 1;
        ans = (ans + cnt * dfs(right + 1) % MOD) % MOD;

        memo.put(i, ans);
        return ans;
    }

    private int bs1(int[] prefix, int l, int r, int target) {
        while (l < r) {
            int m = (l + r) >> 1;
            if (prefix[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    private int bs2(int[] prefix, int l, int r, int target) {
        while (l < r) {
            int m = (l + r) >> 1;
            if (prefix[m] <= target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l - 1;
    }
}

2、 Greedy / DP / Math

然而，其实不难发现一点(也能从上面窥探出来)，其实我们可以只需要记住0...1的个数，然后相乘就行了。

也可以这么想，对于这个问题，可以分成多个子问题，也就是要求解[0,1,...,n - 1]上的分割数组的方式，分割成0...1模式(可能0个0)的多个子字符串，然后解决这些子问题。

class Solution {
    public int numberOfGoodSubarraySplits(int[] nums) {
        int n = nums.length;
        final int MOD = (int)(1e9) + 7;
        long ans = 1;
        int i = 0;
        while (i < n && nums[i] == 0) {
            i++;
        }
        if (i == n) {
            return 0;
        }
        int l = i + 1, r = i + 1;
        while (r < n) {
            if (nums[r] == 1) {
                ans *= (r - l + 1);
                ans %= MOD;
                l = r + 1;
            }
            r++;
        }
        return (int)ans;
    }
}