[Code War記錄] 給定2參數:每個數字位數的總合與數字位數長度,找出區間內所有符合連續位數(由小到大)的數字組合

[Code War記錄] 給定2參數:每個數字位數的總合與數字位數長度,找出區間內所有符合連續位數(由小到大)的數字組合

之前為了訓練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…

只是我寫的這麼長…可見我對這類的邏輯思考似乎不是那麼順暢,有些點倒是想了一下,好像感覺需要圖形化才比較解釋的出來我的想法

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *