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

我正在研究 kata。

按位加法是一种特殊的加法，它不是通常向数字加 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 很大时，它要求超过限制，如果超过，它会说：代码超时

你代码的时间复杂度是 O(k*log(n))，这对于 k 值较大时是不够高效的。这是因为，对于每一次 k 的迭代，你都在本质上迭代了数字 n 中的所有位数。

我们可以通过分析数字加法操作的特点来优化代码：

1. 循环模式 : 注意到每一位数在连续的数字加法操作下会形成一个循环模式。例如，数字 '3' 会经历 '4' -> '5' -> '6' -> '7' -> '8' -> '9' -> '10' -> '11' -> '2' -> '3' 这样一个循环，循环长度为10。

2. 独立性 : 每一位数的循环模式是独立的，不受其他位数的影响。

基于以上两点，我们可以采取以下优化策略:

1. 预计算循环 : 我们可以预先计算出每一位数的循环模式。例如，数字 '3' 的循环模式可以表示为 [4, 5, 6, 7, 8, 9, 1, 0, 1, 2]。

2. 快速跳跃 : 对于每一次 k 操作，我们可以利用预计算的循环模式直接跳到最终结果，而不需要一步一步地进行加法操作。例如，如果 k 是 13，数字是 '3'，那么我们可以直接从预计算的循环模式中找到索引为 13 % 10 = 3 的元素，即 '6'。

优化后的代码:

MOD = 10**9 + 7

def digitwise_addition(n, k):
  cycles = [[(i + j) % 10 for j in range(10)] for i in range(10)]
  new_digits = []
  for digit in str(n):
    digit = int(digit)
    new_digit = cycles[digit][k % 10] 
    new_digits.append(new_digit)
  result = int("".join(map(str, new_digits)))
  return len(str(result)) % MOD

代码解释:

1. cycles : 这是一个二维数组，存储了每一位数的循环模式。 cycles[i][j] 表示数字 i 经过 j 次数字加法操作后的结果。
2. new_digits : 存储最终结果的每一位数字。
3. 对于 n 中的每一位数字，我们使用预计算的循环模式 cycles 直接找到经过 k 次数字加法操作后的结果。
4. 最后，将 new_digits 转换为整数，并返回其位数模 MOD 的结果。

这个优化后的算法的时间复杂度为 O(log(n))，与 k 无关，能够有效地解决 k 值较大的情况。