• Leetcode 2963. Count the Number of Good Partitions
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：2963. Count the Number of Good Partitions

1. 解題思路

這一題根據題意，顯然我們可以將其先分為$n$個原子partition，確保任意兩個partition之間都不存在相同的元素，且每一個partition都不可再進一步切分。

此時，我們的答案總數就是$2^{n?1}$。

因此，我們剩下的問題就是如何切分最小的原子partition了，而這個用一個滑動窗可即可快速得到，也沒啥好多說的了。

2. 代碼實現

給出python代碼實現如下：

class Solution:def numberOfGoodPartitions(self, nums: List[int]) -> int:MOD = 10**9+7locs = defaultdict(list)for i, x in enumerate(nums):locs[x].append(i)cnt = 0max_loc = 0for i, x in enumerate(nums):if i > max_loc:cnt += 1max_loc = locs[x][-1]else:max_loc = max(max_loc, locs[x][-1])cnt += 1ans = pow(2, cnt-1, mod=MOD)return ans

提交代碼評測得到：耗時912ms，占用內存45.1MB。