企业网站制作,icp备案域名网站备案信息,佛山微信网站设计,厦门网站优化服务Leetcode 2963. Count the Number of Good Partitions 1. 解题思路2. 代码实现 题目链接#xff1a;2963. Count the Number of Good Partitions
1. 解题思路
这一题根据题意#xff0c;显然我们可以将其先分为 n n n个原子partition#xff0c;确保任意两个partition之间…Leetcode 2963. Count the Number of Good Partitions 1. 解题思路2. 代码实现 题目链接2963. Count the Number of Good Partitions
1. 解题思路
这一题根据题意显然我们可以将其先分为 n n n个原子partition确保任意两个partition之间都不存在相同的元素且每一个partition都不可再进一步切分。
此时我们的答案总数就是 2 n − 1 2^{n-1} 2n−1。
因此我们剩下的问题就是如何切分最小的原子partition了而这个用一个滑动窗可即可快速得到也没啥好多说的了。
2. 代码实现
给出python代码实现如下
class Solution:def numberOfGoodPartitions(self, nums: List[int]) - int:MOD 10**97locs 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, modMOD)return ans提交代码评测得到耗时912ms占用内存45.1MB。
