之前為了訓練python的語感,去了codewar找題目來練練功,發現了這一題滿有趣的
1.找到所有的數字組合,其每位數的數字加總必須滿足給定的條件值
2.這些數字組合,必須是由小到大連續性的排列組合(例如, 118, 127, 136, 145, 226, 235, 244, 334)
請建立一Function,給定2個參數, x為位數加總的總合,y為預期位數長度,回傳set為3個值,a、b、c,a為滿足的個數,b為滿足的數字中,最小值,c為滿足條件的數字中,最大值
find_all(x, y)
舉例來說:
find_all(10, 3) == [8, 118, 334]
find_all(27, 3) == [1, 999, 999]
這個題目使用窮舉法,其實非常快就寫完了,因為條件是滿清楚的,結果我送出窮舉法的答案後,當server跑了我的程式,帶入它那邊的testcase
結果竟然每次送出都timeout…,原本以為是他們網站的問題,後來看了他的條件,竟然給了8位數長度的條件,以迴圈去跑整個要跑個nx秒,害我好不羞愧
先求有以後,竟然沒有再求好…因此花了一些時間,改寫成字串拼湊的版本…
各位可以參考看看…
def find_all(sum_dig, digs):
max = (10 ** digs)-1
min = (10 ** digs)-1
count = 0
digit_list = ['1' for x in range( 0, digs )]
while int(int(''.join(digit_list))) < 10 ** (digs):
number = int(''.join(digit_list))
#print(number)
sum = 0
for x in digit_list:
sum += int( x )
if sum == sum_dig:
if count == 0:
max = number
min = number
if number > max:
max = number
count += 1
if number == 10 ** (digs) -1:
break
now_index_number = int( digit_list[digs-1] )
if now_index_number == 9:
for index in range(digs-1 , 0, -1):
next_digit_value = int( digit_list[index - 1] )
if next_digit_value < 9:
next_digit_value += 1
for y in range(digs-1, index-2, -1):
digit_list[y] = str(next_digit_value)
break
else:
#digit_list[index] = str( next_digit_value )
continue
continue
digit_list[digs-1] = str( int( digit_list[digs-1] ) + 1 )
if count == 0:
return []
return [count, min, max]
跑出來以後,跟窮舉法計算一下performance,整整差超過100倍以上
不過看了版上神人們的解答後,還是害我無地自容XD,還用遞迴~
隨便舉..
def ways(t, n, d):
return [e for l in [[int(str(i)+str(e)) for e in ways(t-i, n-1, [k for k in d if k>= i])] for i in d] for e in l] if n > 1 else [t] if t in d else []
def find_all(target, n):
r = ways(target, n, [1,2,3,4,5,6,7,8,9])
return [len(r), min(r), max(r)] if r else []
這些人肯定腦中也有安裝python的interpreter…
只是我寫的這麼長…可見我對這類的邏輯思考似乎不是那麼順暢,有些點倒是想了一下,好像感覺需要圖形化才比較解釋的出來我的想法