今天做LeetCode的時候剃袍，發(fā)現(xiàn)這樣一道題黄刚，是簡單的題，不過有一點點奇特
題目讓將一個數(shù)字的各位相加民效，出來的結(jié)果如果不是個位數(shù)憔维，那么就再次相加，直到結(jié)果是個位數(shù)畏邢，這個個位數(shù)就是題目的結(jié)果
原題如下：
最直接的想法是按照這個題意來业扒，如果發(fā)現(xiàn)加出來的結(jié)果不是個位數(shù)，那就再加一遍舒萎，代碼如下：
class Solution {
public int addDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
}
但是它題目下面還有一個要求：不使用循環(huán)和遞歸程储，并且在O(1)時間內(nèi)完成（它寫的是Follow up，我當(dāng)做是必須的要求）
思考一下臂寝，應(yīng)該是有什么規(guī)律章鲤，否則不可能實現(xiàn)這個要求的，所以寫出了一部分?jǐn)?shù)字咆贬，然后發(fā)現(xiàn)結(jié)果是1-9一直循環(huán)败徊，所以將修改了代碼：
class Solution {
public int addDigits(int num) {
if (num < 10)
return num;
num = num % 9;
return num == 0? 9: num;
}
}
提交了之后是正確的，但是我自己現(xiàn)在解釋不了這個代碼掏缎，所以還要再仔細(xì)研究一下這個規(guī)律
考慮兩位數(shù)[10, 100)皱蹦，他們各位數(shù)和的范圍是1-18煤杀，假設(shè)它們都需要兩遍和，第一遍數(shù)字范圍1-18沪哺，第二遍變?yōu)?-9
第一遍：
每增加一個數(shù)怜珍，和也會增加1，假設(shè)sum(x)是x各位數(shù)的和凤粗，那么這時候sum(x+1) = sum(x)+1
較為特殊的是39到40酥泛，前者39 => 12， 后者40 => 4嫌拣，其實是個位數(shù)減9柔袁，十位數(shù)加1，那么它們的各位和符合：sum(x+1) = sum(x) - 9 + 1
綜合來說异逐，第一遍有sum(x+1) = sum(x) + 1或者是sum(x+1) = sum(x) - 9 + 1兩種情況
第二遍：
[1-18]這個范圍內(nèi)sum(x) = x % 9（當(dāng)值為0的時候應(yīng)該取值為9）成立
這樣的話對于兩位數(shù)sum(x+1) = (sum(x)+1) % 9或者是sum(x+1) = (sum(x)+1-9) % 9捶索，對于后邊這個式子，-9可以省略掉灰瞻，所以合并之后就是
sum(x+1) = (sum(x) + 1) % 9 (當(dāng)結(jié)果為0時腥例，取值為9)
這是兩位數(shù)的情況，三位數(shù)的話第一遍和的結(jié)果范圍變?yōu)閇1, 27]酝润，第二遍范圍[1, 18]燎竖，第三遍[1, 9]
...
12位，范圍為[1, 108]要销，第二遍范圍[1, 18]构回，第三遍[1, 9]
...
最終可以得出sum(x+1) = (sum(x) + 1) % 9 (當(dāng)結(jié)果為0時，取值為9)可以一直成立下去
那么sum(x) = x % 9（結(jié)果為0時疏咐，取9）就是成立的纤掸，這就是我第二段代碼的原理
