【LeetCode Day 4】 258. Add Digits [easy][Python]

來自專欄 望美人兮天一方

258. 各位相加 - LeetCode (中國)

給定一個非負整數 num，反覆將各個位上的數字相加，直到結果為一位數。

示例:

輸入：38

輸出：2

因為3+8=11, 11還是兩位數，然後1+1=2，2是一位數

進階:

你可以不使用循環或者遞歸，且在 O(1) 時間複雜度內解決這個問題嗎？

今天畢業拍照，後來又去看房子，回來都差點忘記打卡了！！no！我要堅持打卡咔咔咔！

但一心只想打遊戲/看綜藝的我，就摸魚的挑了一條簡單的題了

思路一：當然是循環。。

執行用時：92 ms (戰勝15.31%)

class Solution: def addDigits(self, num): """ :type num: int :rtype: int """ if len(str(num)) == 1: return num new_num = num while len(str(new_num)) > 1: new_num = sum([int(i) for i in list(str(new_num))]) return new_num

哈哈哈哈哈開心 大概是遇到最簡單的題了 兩分鐘編完 雖然是循環>。<

思路二：盡量O(1)

是我太天真。。寫不出來O(1)的演算法啊。。。然後我又去膜了一下大神代碼。。

（參考自：leetcode258-Add Digits(非負整數各位相加) - CSDN博客）

可以舉例說明一下。

假設輸入的數字是一個5位數字num，則num的各位分別為15897

15897 = 10000*1 + 1000*5 + 100*8 + 10*9 + 1*7

15897 = 1+5+8+9+7 + 9999*1 + 999*5 + 99*8 + 9*9

= 30 + 9999*1 + 999*5 + 99*8 + 9*9

再對30 做同樣的操作

15897 = 30 + 9999*1 + 999*5 + 99*8 + 9*9

= 3*10 + 0*1 + 9999*1 + 999*5 + 99*8 + 9*9

= 3 + （）*9

而：15897-》1+5+8+9+7 = 30 -》 3+0=3 -》 輸出：3

所以我們可以發現，當我們做上面這一系列操作時，最後得到的右邊的餘數3其實就是我們想要的結果，所以我們可以認為把這一系列數字相加得到一個1位數的命題就等同於求num除以9的餘數。

看了賊久才看懂。。。大神！（抱拳）

兩排代碼就搞定了

然後我最開始就直接返回num%9 ，但是其實是有問題的比如18，它就不能直接用num%9....

所以當num%9=0的時候，要麼這個數字加起來為0或者為9

那我們需要考慮有沒有數字可能加起來為0呢？

考慮後，其實除了這個數字本身為0外，是不可能為0，因為沒有負數，所以只要是大於0的數相加怎麼都不可能為0

因此改一下代碼，重新run

執行用時：76 ms (戰勝87.76%)

class Solution: def addDigits(self, num): """ :type num: int :rtype: int """ if num % 9 == 0 and num != 0: return 9 else: return num % 9 ########## 或者可以這麼寫 ###################### if num < 10: return num return (num-1)%9 + 1;

哎 太trick了。。。