該程序必須接受一個(gè)整數(shù) N。該程序必須打印從 10 到 N 的所有步進(jìn)數(shù)字，如果不存在該數(shù)字，則程序應(yīng)打印 -1 作為輸出。如果所有相鄰數(shù)字的絕對差為 1 ，則該數(shù)字稱為 步進(jìn)數(shù)時(shí)限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有什么辦法可以減少執(zhí)行時(shí)間？提前致謝
4 回答
慕桂英4014372
TA貢獻(xiàn)1871條經(jīng)驗(yàn) 獲得超13個(gè)贊
您可以通過注意每次將數(shù)字添加到現(xiàn)有的步進(jìn)數(shù)字時(shí)，它必須比現(xiàn)有的最后一位數(shù)字多 1 或少 1，從而簡化數(shù)字的生成。因此，我們可以生成具有給定位數(shù)的所有步進(jìn)數(shù)字，方法是從單個(gè)數(shù)字 (1-9) 開始，然后向它們重復(fù)添加數(shù)字，直到達(dá)到我們想要的位數(shù)。因此，例如，從 digit 開始1，需要轉(zhuǎn)到 4 位數(shù)字，我們將產(chǎn)生
1 => 10, 12
10, 12 => 101, 121, 123
101, 121, 123 => 1010, 1012, 1210, 1212, 1232, 1234
我們需要的位數(shù)是使用 計(jì)算的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]
請注意，通過將生成的數(shù)字與 進(jìn)行比較，可以加快代碼的運(yùn)行速度，N這樣在調(diào)用時(shí)stepNums(10001)我們就不會(huì)生成直到98989.
牛魔王的故事
TA貢獻(xiàn)1830條經(jīng)驗(yàn) 獲得超3個(gè)贊
也許這里的主要技巧是最大范圍是 10^7。如果我們把每個(gè)數(shù)字看成圖的一個(gè)節(jié)點(diǎn)，我們可以用bfs/dfs遍歷它，在每個(gè)點(diǎn)上，我們只能移動(dòng)到相鄰的節(jié)點(diǎn)（數(shù)字+1，數(shù)字-1）。因?yàn)樽畲笊疃戎挥?7，所以解決方案應(yīng)該很快。
這是一個(gè)粗略的DFS實(shí)現(xiàn)，你可以改進(jìn)細(xì)節(jié)。
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貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超4個(gè)贊
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)
時(shí)間=0.0020003318786621094[s]
[10,12,21,...989898]
步驟編號(hào)定義為“（第 n 位 - n-1 位）= 1 或 -1”。
N 是 10 < N < 10**7。因此，我必須決定第一個(gè)數(shù)字（1or2or..9）和由 1 或 -1 構(gòu)造的 6 dx。
慕桂英546537
TA貢獻(xiàn)1848條經(jīng)驗(yàn) 獲得超10個(gè)贊
因?yàn)槲疫€不能發(fā)表評論。我將在這里解釋尼克算法的思想。
創(chuàng)建 1 位號(hào)碼列表
[1,2,3,4,5,6,7,8,9]通過將 1 位數(shù)字列表中的數(shù)字與 k*10 + (k-1) 或 k*10 + (k+1) 組合來創(chuàng)建 2 位數(shù)字列表
k，例如3將生成32或34重復(fù)步驟 2，直到達(dá)到 m 位數(shù)。
m是之前計(jì)算的。
添加回答
舉報(bào)
0/150
提交
取消