我的简单while循环将计算机挂在较大的输入上

Question

这是我对黑客挑战的回应

https://www.hackerrank.com/challenges/repeated-string

def repeatedString(s, n):
   string = ''
   count = 0

   while len(string) < n:
      for letter in s:
         if len(string) != n:
            string += letter
            if letter == 'a':
               count += 1
   return count

print(repeatedString('aba', 10))
>> 7 # works!

“s”是一个字符串输入，例如“abc”，理论上永远重复n'是无限字符串需要使用的字符数，例如n=10时的'abcabca'

然后，我需要找到“a”的出现次数，我的函数在小整数上运行良好，但对于问题中的测试用例，它们使用100000000000，并且所有东西都超时，甚至在我的笔记本电脑上。你知道吗

有没有一种效率更高、资源消耗更少的方法？你知道吗

Answer 1

你可以做一些数学而不是循环：

def repeatedString(s, n):
   q, r = divmod(n, len(s))
   return s.count('a') * q + s[:r].count('a')

n的值对于这个解决方案并不重要。repeatedString('abca', 100000000000000000000000)只比repeatedString('abca', 10)慢30%。你知道吗