python - 了解 Python 字符串中的重复计数

Question

我面临这个挑战:Repeated String来解决。我一直在尝试解决这个挑战，但由于内存故障而失败。我无法帮助这种情况，因为 HackerRank 平台不支持我的解决方案。可能是32位平台。

我有这个解决方案，这对于长度较小的问题非常有效，但我已经致力于根​​据较少的内存使用来学习这个东西。

我的代码:

def repeatedString(s, n):
   if(s != 'a'):
     return len([x for x in (s*n)[:n] if x == 'a'])

   return n

现在，对于长度和字符串非常大的输入，这会引发内存错误错误。

我对此进行了研究，并看到了一些提交的内容，并发现了这一点。

排行榜的正确解决方案:

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

就是这样!我对这个解决方案感到非常困惑，以至于我无法弄清楚到底发生了什么以及如何发生。有人可以让我知道上述正确的解决方案是如何工作的吗？我是Python新手，正在尽我最大的努力去参与竞争性编码。谢谢!

Answer 1

您的函数抛出内存错误，因为您正在构造一个长度为输入参数 n 的字符串。

n 可以是 10^12，这会产生一个最大长度为 10000 亿个字母的字符串，这意味着您正在创建的字符串可能具有 1 TB 的内存大小(可能更多取决于关于字符串的编码)。

那么必须有另一种方法来计算该大小的字符串中 a 的数量，对吧？

是的(这就是为什么正确答案与您的解决方案不同)。

<小时/>

<强>1。首先我们获取输入字符串的长度。

L = len(s)

例如“abcde”的长度为 5。

<小时/>

<强>2。然后，我们计算 s 中“a”的数量。

s.count('a')

<小时/>

<强>3。接下来，我们想知道在到达长度为 n 的字符串之前 s 整体重复了多少次。

(n//L)

// 运算符称为 integer division ，结果是一个整数。例如，s='abcde' 且 n=14，n//L 等于 2。

<小时/>

<强>4。将 s 中“a”的数量乘以 s 可以放入长度为 n 的字符串的次数。

s.count('a') * (n//L)

<小时/>

<强>5。我们快完成了，但对于我们的例子来说，仍然缺少一些东西。 'abcde' 可以在长度为 n 的字符串中重复两次，但在我们的示例中为 'abcd'，仍然剩下 4 个字符。

在这里，我们使用 s[:n % L] 从 s 构造剩余的字符串，或者在我们的示例中使用 s[:14 % 5] 或 s[:4]，结果为 'abcd'。

然后我们用 s[:n % L].count('a') 计算该字符串中 'a' 的数量

<小时/>

<强>6。将它们加在一起，我们就得到了您答案中的函数:

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