我上周在技术评估时遇到了这个问题。我不知道我做错了什么。
给定一个大小为 n 的整数列表,找到权重范围为 1, 2, ..., n 的连续子串的数量。子字符串的权重是字符串包含的不同整数的数量。例如,权重('1') = 1,权重('1 1') = 1,权重('2 1') = 2。
当输入字符串为“1 1 2”时,输出将为“4 2 0”。 n 为 3,我们需要找到权重为 1、2、3 的子串的数量。对于权重为 1 的连续子串,有 4 个子串:'1'、'1'、'2' 和 1 1' 。对于权重为 2 的连续子串,有 2 个子串:'1 2' 和 1 1 2'。对于权重为 3 的连续子串,有 0 个子串。
我的Python代码只能通过40%的测试用例:
import collections
def substringWeights(s):
n = len(s)
substrings = []
for i in range(n):
for j in range(i+1, n+1):
substrings.append(s[i:j])
weight = collections.defaultdict(int)
for i in range(1, n+1):
weight[i] = 0
for item in substrings:
weightValue = len(set(item))
weight[weightValue] += 1
res = weight.values()
res.sort(reverse = True)
res = list(map(str, res))
return ' '.join(res)
这里我首先生成所有子字符串,然后计算每个子字符串的weightValue并使用defaultdict记录数字。
不知道为什么我做错了。请帮忙!!!预先感谢!
我认为你可以使用滑动窗口的方法来使计算更加高效。对于 s 的每个 K 大小的子字符串(其中
1 <= K <= len(s)
),您可以使用字典创建一个从索引 0 开始到索引 K - 1 的 K 大小滑动窗口,以跟踪窗口中的唯一字符出现计数(window
)下面的代码),然后迭代字符串(即 1 - K
-> 2 - (K + 1)
-> ...),对于每次迭代,window
字典减去前一个窗口的第一个字符,如果它为零则删除键。这样您就可以有效地跟踪 s 的每个可能子字符串的唯一字符计数,并随时更新权重计数
def substringWeights(s):
weights = [0] * len(s)
for i in range(1, len(s) + 1):
window = collections.defaultdict(lambda : 0)
for j in range(i):
window[s[j]] += 1
weights[len(window) - 1] += 1
for j in range(i, len(s)):
window[s[j - 1]] -= 1
window[s[j]] += 1
if window[s[j - 1]] == 0:
window.pop(s[j - 1])
weights[len(window) - 1] += 1
return ' '.join([str(x) for x in weights])