[容易]569.皆さん加算

私は小強です.これは私の7編目のオリジナル文章で、読むのに約10分かかります.
タイトル
LintCode:皆さん加算
説明
非負の整数numが与えられ、1ビットの整数が得られるまで、すべてのビットの数字を繰り返し加算する.
サンプルnum = 38が与えられる.加算の手順は、3 + 8 = 111 + 1 = 2です.2は1つの数字しか残っていないので、2を返します.
構想
問題は皆さんに加算することを要求して、当然な構想は毎回10を除いて、それから余剰を加算して、10に整除されないまで、それから最後の余剰を加算します.
インプリメンテーション
再帰的な実装

java実装

public class Solution {
    /**
     * @param num a non-negative integer
     * @return one digit
     */
    public int addDigits(int num) {
        // Write your code here
        int sum = 0;
        while(num / 10 >= 1){
            sum += num % 10;
            num /= 10;
        }
        sum += num % 10;
        if (sum >= 10)
            sum = addDigits(sum);
        return sum;
    }
}

結果分析結果:結果はLintCodeの要求を通過した.分析:このような実現は理解しやすいが、実現するには巧みなところはない.そして時間が遅い.

その他の最適化リファレンス
LintCode:569各位加算LeetCode discuss
数学の原理
https://en.wikipedia.org/wiki/Digital_root [Step 1]:

438  == 40*10 +3*10 +8 ;
4+3+8 == 4*(10%9)*(10%9)+3*(10%9)+8%9= 15   ;

[Step 2]:

15  == 1*10 + 5 ; 
1+5 == 1*(10%9)+5%9= 6 ;

[So we can see]:

ab%9%9%9==ab%9; 
just return num%9; and don't forget num==0 or num==9   

優秀なコード

public class Solution {
    public int addDigits(int num) {
        return num==0?0:(num%9==0?9:(num%9));
    }
}