分享一道笔试题目(字符串算法题)
分享一道当时笔试中没做出来的算法题。（搜了一下网上好像没有这道题的解法，提供一下个人后来想的思路）
定义“好字符串”为该字符串中出现字母的频率相等（如："abba"是好字符串，因为"a"和"b"出现频率均为2）。
给定一个字符串，求其“好子序列”的个数。（子序列即从最初的序列通过去掉某些元素但不破坏余下元素的相对位置而形成的新序列）
例子：给定字符串 "abca"
好子序列个数为13个（即 a, b, ab, c, ac, bc, abc, a, aa, ba, ca, bca, 空字符串）
思路：1- 先求出给定字符串（"abca"）中所有字母出现的频率，即count = {"a":2, "b":1, "c":1}
2- 求出最大的频率 max_freq = max(count.values())，枚举频率k从1到max_freq，尝试构造“好子序列”
3- 对于某个频率k, 每种字母 i 的选取总共有 C (count[i], k) + 1 种可能 （其中+1指的是不选取该字母i）
4- 然后将所有字母的选取可能相乘，最后再 -1 （-1表示减去 所有字母都不选，空字符串的情况）
python代码
def comb(n,m): #求组合数 return math.factorial(n)//(math.factorial(m)*math.factorial(n-m)) def countGoodSubsequences(word:str): res = 0 count = Counter(word) max_freq = max(count.values()) for k in range(1, max_freq+1): #枚举从1到最大频率的所有情况 cnt = [] for v in count.values(): if v < k: continue #如果当前字符的频率小于k，不用考虑 cnt.append(comb(v,k)+1)#求当前字符的频率为k的组合数+1 (+1表示空字符的情况) res += (math.prod(cnt)-1) #求所有字符的频率为k的组合数的乘积(-1表示去掉全空字符串的情况) return res+1 #最后加上空字符串的情况不知道是否还有复杂度更低的思路。
投递深圳同为数码等公司10个岗位
网易公司福利 153人发布