該程序必須接受一個整數 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有什么辦法可以減少執行時間？提前致謝
4 回答
慕桂英4014372
TA貢獻1871條經驗 獲得超13個贊
您可以通過注意每次將數字添加到現有的步進數字時，它必須比現有的最后一位數字多 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.
牛魔王的故事
TA貢獻1830條經驗 獲得超3個贊
也許這里的主要技巧是最大范圍是 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
Helenr
TA貢獻1780條經驗 獲得超4個贊
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。
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
因為我還不能發表評論。我將在這里解釋尼克算法的思想。
創建 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是之前計算的。
添加回答
舉報
0/150
提交
取消