使用python从10到N的步数

Question

该程序必须接受一个整数 N。该程序必须打印从 10 到 N 的所有步进数字，如果不存在该数字，则程序应打印 -1 作为输出。如果所有相邻数字的绝对差为 1 ，则该数字称为 步进数时限code Works perfectlymaximum possible test casebrute forcedef 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 1a=int(input())if a<10:    print(-1)# brute force approach to iterate all the integers from 10 to afor i in range(10,a+1):    if isStepNum(i):        print(i,end=" ")Boundary   : 1<=N<=10^7Time Limit : 500 ms例子：Input : 12 Output : 10 12Input : 100Output: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98Input : 5Output : -1有什么办法可以减少执行时间？提前致谢

Answer 1

您可以通过注意每次将数字添加到现有的步进数字时，它必须比现有的最后一位数字多 1 或少 1，从而简化数字的生成。因此，我们可以生成具有给定位数的所有步进数字，方法是从单个数字 (1-9) 开始，然后向它们重复添加数字，直到达到我们想要的位数。因此，例如，从 digit 开始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.

Answer 2

也许这里的主要技巧是最大范围是 10^7。如果我们把每个数字看成图的一个节点，我们可以用bfs/dfs遍历它，在每个点上，我们只能移动到相邻的节点（数字+1，数字-1）。因为最大深度只有 7，所以解决方案应该很快。

这是一个粗略的DFS实现，你可以改进细节。

sol_list = []

def dfs(i, num, N):

  # print(i, num)

  if num > N: # too much, need to break

    return

  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

    global sol_list

    # print(num)

    sol_list.append(num) # add to solution

  if i > 7:

    return

  if num == 0: # I can call another 0

    dfs(i+1, 0, N) # this is not needed if the numbers are added in the previous list without checking

  last_dig = num % 10

  if last_dig == 0:

      dfs(i+1, num*10 + 1, N) # if last digit is 0, we can only choose 1 as next digit not -1

  elif last_dig == 9:

    dfs(i+1, num*10 + 8, N)

  else:

    dfs(i+1, num*10 + (last_dig-1), N)

    dfs(i+1, num*10 + (last_dig+1), N)

import time

t1 = time.time()

[dfs(0, i, 10000000) for i in range(10)] # staring with every digit possible 0-9

t2 = 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 product

from itertools import accumulate

import time

def main(n):

    result=set()

    for length in range(2,7):

        dxss=list(product([-1,1],repeat=length-1))

        for initial in range(1,10):

            for dxs in dxss:

                ans=list(accumulate(dxs,initial=initial))

                if all([(y in range(0,10)) for y in ans]):

                     result.add(int("".join(map(str,ans))))

    sorted_lst=sorted(result)

    return [x for x in sorted_lst if x<n]

n=10000000

start=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 位号码列表[1,2,3,4,5,6,7,8,9]

2. 通过将 1 位数字列表中的数字与 k*10 + (k-1) 或 k*10 + (k+1) 组合来创建 2 位数字列表k，例如3将生成32或34

3. 重复步骤 2，直到达到 m 位数。m是之前计算的。