时间戳

首页 > 解决方案 > 了解 Python 字符串中的重复计数

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

问题描述

我有这个挑战：重复字符串来解决。我一直在努力解决这个挑战，但得到了Memory Failure的失败 cos 。我无法解决这种情况，因为 HackerRank 平台不支持我的解决方案。可能是 32 位平台。

我有这个解决方案，它非常适用于长度较小的问题，但我已经研究过这个东西，以根据更少的内存使用来学习。

我的代码：

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

   return n

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

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

排行榜的正确解决方案：

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

而已！我对这个解决方案感到非常困惑，以至于我可以弄清楚实际发生了什么以及如何发生。有人可以让我知道上述正确解决方案的工作原理吗？我是 python 新手，并尽我所能在竞争性编码方面有所作为。谢谢你！

标签： pythonstring

解决方案

您的函数抛出内存错误，因为您正在构造一个长度为输入参数 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)

该//运算符称为整数除法，它产生一个整数。例如 s='abcde' 和 n=14，n//L等于 2。

4. 将 s 中的 'a' 的数量乘以 s 可以放入长度为 n 的字符串的次数。

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

5. 我们几乎完成了，但是对于我们的示例，仍然缺少一些东西。'abcde' 可以在长度为 n 的字符串中重复两次，但还剩下 4 个字符，在我们的示例中为 'abcd'。

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

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

6.把它们加在一起，我们得到你答案中的函数：

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

推荐阅读