python - 使用 python 从 10 到 N 的步数

Question

The Program must accept an integer N. The program must print all the stepping number from 10 to N, if there is no such number present the program should print -1 as the output .

A number is called stepping number if all adjacent digits have an absolute difference of 1
The code Works perfectly I just need to reduce the time limit for the maximum possible test case I wrote the code in python where i approached this problem using brute force, but the code didn't succeed because of the time limit

def isStepNum(n):
    lst_num = str(n)
    for i in range(len(lst_num)-1):
        if abs(int(lst_num[i])-int(lst_num[i+1]))!=1:
            return 0
    return 1
a=int(input())
if a<10:
    print(-1)
# brute force approach to iterate all the integers from 10 to a
for i in range(10,a+1):
    if isStepNum(i):
        print(i,end=" ")

Boundary   : 1<=N<=10^7
Time Limit : 500 ms

示例:

Input : 12 
Output : 10 12

Input : 100
Output: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

Input : 5
Output : -1

有什么办法可以减少执行时间吗？提前致谢

Answer 1

您可以通过注意每次将数字添加到现有的步进数字时，它必须比现有的最后一位数字多 1 或少 1 来简化数字的生成。因此，我们可以通过从单位数字(1-9)开始，然后重复向其添加数字，直到达到我们想要的位数，来生成具有给定位数的所有步进数字​​。例如，从数字 1 开始，需要转到 4 位数字，我们将生成

1 => 10, 12
10, 12 => 101, 121, 123
101, 121, 123 => 1010, 1012, 1210, 1212, 1232, 1234

我们需要的位数是使用math.ceil(math.log10(N))计算的。

import math

def stepNums(N):
    if N < 10:
        return -1
    digits = math.ceil(math.log10(N))
    sn = [[]] * digits
    # 1 digit stepping numbers
    sn[0] = list(range(1, 10))
    # m digit stepping numbers
    for m in range(1, digits):
        sn[m] = []
        for s in sn[m-1]:
            if s % 10 != 0:
                sn[m].append(s * 10 + s % 10 - 1)
            if s % 10 != 9:
                sn[m].append(s * 10 + s % 10 + 1)
    return [s for l in sn for s in l if 10 <= s <= N]

例如

print(stepNums(3454))

输出:

[10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98, 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 432, 434, 454, 456, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989, 1010, 1012, 1210, 1212, 1232, 1234, 2101, 2121, 2123, 2321, 2323, 2343, 2345, 3210, 3212, 3232, 3234, 3432, 3434, 3454]

请注意，通过将生成的数字与 N 进行比较，代码可能会加速，这样在调用 stepNums(10001) 时，我们就不会生成所有数字至 98989。