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

一、本周周赛总结

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

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

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

1. 题目描述

2. 思路分析

和T2是同题。
1

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

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)
1
2
3

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

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

1. 题目描述

2. 思路分析

同T1
1

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])
1
2
3

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

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

1. 题目描述

2. 思路分析

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

3. 代码实现

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        ans = s = 0
        q = deque()
        cnt = Counter()
        for v in nums:
            q.append(v)
            cnt[v] += 1
            s += v
            if len(q) > k:
                p = q.popleft()
                cnt[p] -= 1
                if not cnt[p]:
                    del cnt[p]
                s -= p
            if len(q) == k and len(cnt)>=m:
                ans = max(ans,s)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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 0
        cc = sorted([(v,p) for p,v in cnt.items()],reverse=True)
        
        ans = 1         
        big = 0
        for v,_ in cc:
            if v > cc[k-1][0]:
                ans = ans * v % MOD
                big += 1
            else:
                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) %MOD
        return ans               
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考链接