LeetCode Biweekly Contest 166

发表于 更新于 本文字数： 405 阅读时长 ≈ 1 分钟

本文介绍解决此次比赛中题目（3692 - 3695）的思路与想法。

3692. Majority Frequency Characters

题目大意

给一个字符串 s，对于 s 中出现的每一个字母，假设其出现的次数为 k，则其属于 frequency group k。问在所有的 frequency group 中，包含字符数最多（如果相同则选择 k 更大的）的那一组中包含了什么字母。可以使用任意顺序输出组中的字母。

思路

s.length 较小可以直接模拟 / 暴力

先统计每一个字符出现的次数

1
2
3
char_freqs = [0 for _ in range(26)] # char_freqs[i] 表示 'a' + i 这个字符出现的次数
for char in s:
    char_freqs[ord(char) - ord('a')] += 1

接着将出现次数相同的字符添加到同一个组里

1
2
3
4
freq_groups = [[] for _ in range(100 + 1)] # 由于 len(s) <= 100，则一个字符最多出现100次，于是 k <= 100，可以用数组解决。若 k 过大可以使用 dict
for i in range(26):
    char_freq = char_freqs[i]
    freq_groups[char_freq].append(chr(i + ord('a')))

为了避免将从未出现的字母添加到 freq_groups[0] 中，添加一个小小的判断，或者在下面统计组中字母数量时使用 range(1, 101)

1
2
if char_freq != 0:
    freq_groups[char_freq].append(chr(i + ord('a')))

最后就是统计每个组里字母的数量了

1
2
3
4
5
6
ans_idx = -1
ans_len = -1
for i, freq_group in enumerate(freq_groups):
    if len(freq_group) >= ans_len: # 为了使两个组长度相同时，输出 k 较大的那一个，使用大于等于号
        ans_len = len(freq_group)
        ans_idx = i

输出！

1
return ''.join(freq_groups[ans_idx])

复杂度

O(len(s))

3693. Climbing Stairs II

3694. Distinct Points Reachable After Substring Removal

3695. Maximize Alternating Sum Using Swaps