Leetcode 2963. Count the Number of Good Partitions

[Woodyiiiiiii]

2963. Count the Number of Good Partitions

2963. Count the Number of Good Partitions

参考资料：
合并区间的两种写法（Python/Java/C++/Go）

相关区间题目：
56. Merge Intervals
55. Jump Game
2580. Count Ways to Group Overlapping Ranges
2584. Split the Array to Make Coprime Products

这道题我一开始想到用DP去做，想用记忆化搜索，但没有思路，因为需要循环；如果用递推，依然不行，因为f(n+1)无法从f(n)中推算得出。

所以这道题要转换思路，想要满足题目要求，要先找到一个数的首次出现和末次出现，然后形成一个个区间，其中交叉的区间需要合并，最后形成互不交叉的区间，从这些m个区间中，之间的屏障选或不选，所以最后是2^(m-1)。

import java.math.BigInteger;

class Solution {
    public int numberOfGoodPartitions(int[] nums) {
        int MOD = 1000000007;
        int n = nums.length;
        // find the left most and right most index of each number
        Map<Integer, Integer> leftMostMap = new HashMap<>(), rightMostMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (!leftMostMap.containsKey(num)) {
                leftMostMap.put(num, i);
            } else {
                rightMostMap.put(num, i);
            }
        }
        // create intervals
        List<List<Integer>> intervals = new ArrayList<>();
        for (int num : leftMostMap.keySet()) {
            int left = leftMostMap.get(num), right = rightMostMap.getOrDefault(num, left);
            List<Integer> interval = new ArrayList<>();
            interval.add(left);
            interval.add(right);
            intervals.add(interval);
        }
        intervals.sort(Comparator.comparingInt(a -> a.get(0)));
        // merge intervals
        int cnt = 1;
        List<Integer> cur = Arrays.asList(0, 0);
        for (List<Integer> interval : intervals) {
            if (interval.get(0) <= cur.get(1)) {
                cur.set(1, Math.max(cur.get(1), interval.get(1)));
            } else {
                cur = interval;
                cnt++;
            }
        }
        // return 2^ (cnt - 1)
        return BigInteger.valueOf(2).modPow(BigInteger.valueOf(cnt - 1), BigInteger.valueOf(MOD)).intValue();
    }
}

1. 转换思维，DP不行的话就要放弃
2. 拓展思维，题目多个方法多维度去解
3. 从目的出发，转换题意

More practice, More thinking.