南昌房产网站建设,网站建设和app开发,做外贸网站赚钱吗,四大战略咨询公司Leetcode 3003. Maximize the Number of Partitions After Operations 1. 解题思路2. 代码实现 题目链接#xff1a;10038. Maximize the Number of Partitions After Operations
1. 解题思路
这一题我看实际比赛当中只有72个人做出来#xff0c;把我吓得够呛#xff0c;…Leetcode 3003. Maximize the Number of Partitions After Operations 1. 解题思路2. 代码实现 题目链接10038. Maximize the Number of Partitions After Operations
1. 解题思路
这一题我看实际比赛当中只有72个人做出来把我吓得够呛还以为会很难不过实际做了之后发现其实挺简单的不知道啥情况……
思路上来说这道题还是动态规划的思路要考虑能够分割的partition的最大数目我们只需要考察每一位上的字符是否需要发生变化以及变化前后分割数目的变化即可。
显然如果一个字符在当前的partition当中没有出现过那么这个字符显然不需要进行变化因为不会因此而产生额外的收益。
而如果该字符在当前partition当中已经出现过但是变化的次数已经过了那么我们同样不需要进行考虑只能顺序进行partition的切分看看能分割成多少个partition。
而如果该字符在当前partition当中已经出现过且变换的机会还没使用我们就要遍历一下将其变换成所有当前partition当中还未出现过的字符以及保留变换机会不在此进行变换的情况下能够获得的partition的最大值返回即可。
而关于当前partition当中已出现过哪些字符我们可以用一个int值来记录一下各个字符是否已经有出现过。
此时总的时间复杂度就是 O ( 26 × 2 × N ) O(26 \times 2 \times N) O(26×2×N)。
2. 代码实现
给出python代码实现如下
class Solution:def maxPartitionsAfterOperations(self, s: str, k: int) - int:if len(set(s)) k or k 26:return 1n len(s)lru_cache(None)def dp(idx, change, status):if idx n:return 0 if status 0 else 1loc ord(s[idx]) - ord(a)if status (1loc) 0:if Counter(bin(status))[1] k:return 1 dp(idx, change, 0)else:return dp(idx1, change, status | (1loc))else:ans dp(idx1, change, status)if change 0:if Counter(bin(status))[1] k:for i in range(26):if status (1 i) 0:ans max(ans, 1 dp(idx1, change-1, 1 i))else:for i in range(26):if status (1 i) 0:ans max(ans, dp(idx1, change-1, status | (1 i)))return ansreturn dp(0, 1, 0)提交代码评测得到耗时719ms占用内存119.8MB。
