[LeetCode周赛复盘] 第 112场双周赛20230903

一、本周周赛总结

• 这场wa好多次，幸好没打。
• T1 模拟。
• T2 模拟。
• T3 滑窗。
• T4 组合数学。
  

2839. 判断通过操作能否让字符串相等 I

2839. 判断通过操作能否让字符串相等 I

1. 题目描述

2. 思路分析

和T2是同题。

• 可以两两交换的话，意味着奇数/偶数内部可以任意交换顺序，那么只要两个串的奇数和奇数相同，偶数和偶数相同即可。

3. 代码实现

class Solution:def canBeEqual(self, s1: str, s2: str) -> bool:return Counter(v for i,v in enumerate(s1) if i&1) == Counter(v for i,v in enumerate(s2) if i&1) and  Counter(v for i,v in enumerate(s1) if not i&1) == Counter(v for i,v in enumerate(s2) if not i&1)

2840. 判断通过操作能否让字符串相等 II

2840. 判断通过操作能否让字符串相等 II

1. 题目描述

2. 思路分析

同T1

3. 代码实现

class Solution:def checkStrings(self, s1: str, s2: str) -> bool:return Counter(s1[::2]) == Counter(s2[::2]) and  Counter(s1[1::2]) == Counter(s2[1::2])

2841. 几乎唯一子数组的最大和

2841. 几乎唯一子数组的最大和

1. 题目描述

2. 思路分析

• 滑窗，计数窗口内不同元素个数即可。

3. 代码实现

class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:ans = s = 0q = deque()cnt = Counter()for v in nums:q.append(v)cnt[v] += 1s += vif len(q) > k:p = q.popleft()cnt[p] -= 1if not cnt[p]:del cnt[p]s -= pif len(q) == k and len(cnt)>=m:ans = max(ans,s)return ans

2842. 统计一个字符串的 k 子序列美丽值最大的数目

2842. 统计一个字符串的 k 子序列美丽值最大的数目

1. 题目描述

2. 思路分析

• k序列必须字符唯一，因为s中至少要有k个不相同的字符，否则返回0。
• 要求美丽值最大的话，显然优先取出现次数更多的k种字符。
• 记这k种字符的次数分别是c1,c2…ck，那么方案数就是这些次数的乘积。
• 但要处理第k种字符，可能有m个字符和这个字符次数相同，要考虑一个组合问题。
• 假设一共有m种字符出现次数是ck，在前k大里，有r中字符出现次数是ck，那么有C(m,r)种选择方案。

3. 代码实现

MOD = 10**9+7
class Solution:def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:cnt = Counter(s)if k > len(cnt): return 0cc = sorted([(v,p) for p,v in cnt.items()],reverse=True)ans = 1         big = 0for v,_ in cc:if v > cc[k-1][0]:ans = ans * v % MODbig += 1else:break ck = list(cnt.values()).count(cc[k-1][0])# print(ans * pow(cc[k-1][0],k-big,MOD)%MOD, big ,ck)ans = ans * pow(cc[k-1][0],k-big,MOD)%MOD* comb(ck,k-big) %MODreturn ans               

参考链接