Digitwise_addition：超出限制：如果超出 -> 代码超时

Question

我正在练习型。

按位加法是一种特殊的加法，它不是通常给数字加 1，而是给该数字的每个数字加 1。如果该数字是 9，我们将其替换为 10，而不保留到下一个数字。

示例

123 -> 234

任务

编写一个函数，该函数接受两个数字 n 和 k，并在应用按位加法 k 次后输出 n 中的位数。由于答案可能非常大，因此返回对 1_000_000_007 取模的答案。

您的解决方案预计为 O(klogn)。

我的解决方案：

import sys
MOD = 10**9 + 7 

sys.set_int_max_str_digits(0)

def d2a(digits):

  arr= list(map(int,str(digits)))
  return arr


def a2d(arr):
  length=len(arr)
  digit=""

  for i in range(length):
    digit+=str(arr[i])
  return int(digit)


def add(n):
  return n+1


def digitwise_addition(digit, K):
  for i in range(K):
    #CONVERTING INTO ARRAY
    arr=d2a(digit)
    #ADDING 1 INTO ALL NUMBERS FROM ARRAY
    arr=list(map(add,arr))
    #CONVERTING ARRAY INTO DIGIT
    digit=a2d(arr)

  arr=d2a(digit)
  return len(arr) %MOD

问题：它通过了所有计算，但是当K很大时，它要求超出限制，如果超出，则提示：代码超时

Answer 1

在循环中，

digit

字符串变得越来越长，这会减慢进程。它使得时间复杂度比 O(𝑘log𝑛) 更差。

您可以利用以下见解：

• 加 1 时，每个数字只需要处理 10 种不同的情况，因此您可以维护每个数字有多少个数字，而不是单独存储每个数字。

• 在每次迭代中，“2”位数与之前的“1”位数相同。其他数字类似（其中“0”的数量成为您之前拥有的“9”的数量），只不过“1”的数量是您拥有的“0”和“9”的数量之和之前。

以下是如何转化为代码：

from collections import deque

MOD = 10**9 + 7 

def digitwise_addition(n, k):
    digits = deque([0] * 10)
    for digit in str(n):
        digits[int(digit)] += 1
    for i in range(k):
        digits.rotate()
        digits[1] += digits[0]
            
    return sum(digits) % MOD