LeetCode 258. Add Digits

1379 ワード

比較的興味深い解法アルゴリズムを理解するために、毎日いくつかのLeetCodeの上の問題を見ることにしました.今から始めます.問題:Given a non-negative integer num、repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
タイトルの大まかな意味は:非負の整形数字があって、そのすべての桁数を加えて新しい数字を得て、もし得た新しい数字が1桁でなければ、この過程を繰り返して、1桁まで;
この問題を手に入れたのは当然だと思っていたが、問題が一つ要求されたのを見て、何がどうしたのか分からなかった.この問題の要求は:Follow up:Could you do it without any loop/recursion in O(1)runtime?再帰的または循環的に実現しないことができ、アルゴリズムの時間はO(1)である.
だからこのテーマは数字の法則の問題かもしれないと思います.それからLeetCodeは考えをあげました.ウィキペディアの上の文章は、digital rootについての文章です.記事のURLは次のとおりです.https://en.wikipedia.org/wiki/Digital_root
この文章の内容、つまり数式に基づいて、次のコードを書きました.
class Solution {
public:
    int addDigits(int num) {
        if(num>0)
        return num-9*(int)((num-1)/9);
        else
        return 0;
    }
};