字符串中字符频率的优化计数器

Question

我正在解决这问题，这个问题需要计算字符串中的'a's数，然后对其进行操作，直到第6行。

我想出的解决办法是：

s='abcac'
n=52
x=n//len(s)
y=n%len(s)
k=s[:y]
s=(s*x)+k
from collections import Counter
print(s.count('a'))

-很简单很简单但是当n是一个大的数(例如1000000000000 )时，它就会产生误差。

如何优化我的解决方案？提前谢谢。

Answer 1

您不需要构建扩展字符串。首先，计算适合于n字符：n//len(s)的字符串的完整重复次数。然后将此计数乘以字符串中的"a“数。有了它之后，只需计算出还需要多少字符串才能覆盖剩余的n字符：n%len(s)，并计算该子字符串中"a“的数量：

因此，结果将是：

 n//len(s)*s.count("a") + s[:n%len(s)].count("a")

Answer 2

你提到“当n是一个很大的数(例如1000000000000)时，它会产生错误。”让我们看看我们在做什么.

变量n是我们所关心的字符数。此外，基于x = n // len(s)，x是我们将遇到的字符串s的完整重复数，而y是一个处理任何“剩余”/“溢出”字母的子字符串。

现在，对我来说，一个很大的危险是像s = (s * x) + k一样。从语法上讲，这是一个很好的- python，它支持整数乘的字符串。但是让我们看看我的解释器在运行您的代码时会发生什么，并使n变得非常大.

>>> string * 10000000000000000
python(<pid>,<memory-address>) malloc: *** mach_vm_map(size=10000000000004096) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError
>>>

当我们生成这样的扩展字符串时，如果字符串的每个字符都是1字节(为了简单起见，我们假设仅使用ASCII字符)，则需要内存来存储- and，这一行需要10^12或大约1TB的信息！这不可行。

我认为这里的挑战是想出一个不需要你实际做字符串的解决方案--有一些数学方法可以计算'a's在无限字符串中的数量，因为你知道它的子结构。

作为参考，以下是我的解决方案：

def repeatedString(s, n):
    num_a_in_substring = s.count('a')
    n_repetitions = n // len(s)
    overflow = s[:n%len(s)]
    return (num_a_in_substring * n_repetitions) + overflow.count('a')

请注意，我不是在内存中创建一个巨大的10^12字符字符串的版本，而是在较小的字符串中计算a的数量，并根据这个结果进行构建。那样的话，我只是在玩弄一个数字，而不是一根巨大的绳子。

希望这能有所帮助。

Answer 3

from collections import Counter
s='a'
n=100000
a=s.count('a')
x=n//len(s)
y=n%len(s)
k=s[:y]
b=k.count('a')
#s=(s*x)+k
print((a*x)+b)

我把代码改成了这个，它就成功了。非常感谢大家的帮助。

很明显的解决办法，不知何故我错过了。