使用python从10到N的步数

Question

该程序必须接受一个整数 N。该程序必须打印从 10 到 N 的所有步进数字，如果不存在该数字，则程序应打印 -1 作为输出。

如果所有相邻数字的绝对差为 1 ，则

该数字称为 步进数时限code Works perfectlymaximum possible test casebrute force

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) 开始，然后向它们重复添加数字，直到达到我们想要的位数。因此，例如，从 digit 开始1，需要转到 4 位数字，我们将产生1 => 10, 1210, 12 => 101, 121, 123101, 121, 123 => 1010, 1012, 1210, 1212, 1232, 1234我们需要的位数是使用 计算的math.ceil(math.log10(N))。import mathdef stepNums(N):&nbsp; &nbsp; if N < 10:&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; digits = math.ceil(math.log10(N))&nbsp; &nbsp; sn = [[]] * digits&nbsp; &nbsp; # 1 digit stepping numbers&nbsp; &nbsp; sn[0] = list(range(1, 10))&nbsp; &nbsp; # m digit stepping numbers&nbsp; &nbsp; for m in range(1, digits):&nbsp; &nbsp; &nbsp; &nbsp; sn[m] = []&nbsp; &nbsp; &nbsp; &nbsp; for s in sn[m-1]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if s % 10 != 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sn[m].append(s * 10 + s % 10 - 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if s % 10 != 9:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sn[m].append(s * 10 + s % 10 + 1)&nbsp; &nbsp; 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.

Answer 2

也许这里的主要技巧是最大范围是 10^7。如果我们把每个数字看成图的一个节点，我们可以用bfs/dfs遍历它，在每个点上，我们只能移动到相邻的节点（数字+1，数字-1）。因为最大深度只有 7，所以解决方案应该很快。这是一个粗略的DFS实现，你可以改进细节。sol_list = []def dfs(i, num, N):&nbsp; # print(i, num)&nbsp; if num > N: # too much, need to break&nbsp; &nbsp; return&nbsp; if num <= N and num >= 10: # perfect range, add to solution, I can add some repeated solution as I called dfs(i+1,0,N) multiple times&nbsp; &nbsp; global sol_list&nbsp; &nbsp; # print(num)&nbsp; &nbsp; sol_list.append(num) # add to solution&nbsp; if i > 7:&nbsp; &nbsp; return&nbsp; if num == 0: # I can call another 0&nbsp; &nbsp; dfs(i+1, 0, N) # this is not needed if the numbers are added in the previous list without checking&nbsp; last_dig = num % 10&nbsp; if last_dig == 0:&nbsp; &nbsp; &nbsp; dfs(i+1, num*10 + 1, N) # if last digit is 0, we can only choose 1 as next digit not -1&nbsp; elif last_dig == 9:&nbsp; &nbsp; dfs(i+1, num*10 + 8, N)&nbsp; else:&nbsp; &nbsp; dfs(i+1, num*10 + (last_dig-1), N)&nbsp; &nbsp; dfs(i+1, num*10 + (last_dig+1), N)import timet1 = time.time()[dfs(0, i, 10000000) for i in range(10)] # staring with every digit possible 0-9t2 = time.time()print(t2-t1)sol = sorted(set(sol_list))print(sol) # added some repeated solutions, it's easier to set them

Answer 3

from itertools import productfrom itertools import accumulateimport timedef main(n):&nbsp; &nbsp; result=set()&nbsp; &nbsp; for length in range(2,7):&nbsp; &nbsp; &nbsp; &nbsp; dxss=list(product([-1,1],repeat=length-1))&nbsp; &nbsp; &nbsp; &nbsp; for initial in range(1,10):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for dxs in dxss:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans=list(accumulate(dxs,initial=initial))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if all([(y in range(0,10)) for y in ans]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;result.add(int("".join(map(str,ans))))&nbsp; &nbsp; sorted_lst=sorted(result)&nbsp; &nbsp; return [x for x in sorted_lst if x<n]n=10000000start=time.time()lst=main(n)stop=time.time()print("time={0}[s]".format(stop-start))print(lst)时间=0.0020003318786621094[s][10,12,21,...989898]步骤编号定义为“（第 n 位 - n-1 位）= 1 或 -1”。N 是 10 < N < 10**7。因此，我必须决定第一个数字（1or2or..9）和由 1 或 -1 构造的 6 dx。

Answer 4

因为我还不能发表评论。我将在这里解释尼克算法的思想。创建 1 位号码列表[1,2,3,4,5,6,7,8,9]通过将 1 位数字列表中的数字与 k*10 + (k-1) 或 k*10 + (k+1) 组合来创建 2 位数字列表k，例如3将生成32或34重复步骤 2，直到达到 m 位数。m是之前计算的。