LeetCode 258各位相加

• 题目简述：给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

• 输入：38 输出：2 解释：各位相加：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2

• 思路一：模拟计算过程O(logn)

class Solution {
public:
    int addDigits(int num) {
        while(num >= 10)
        {
            int sum = 0;
            while(num)
            {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
};

• 思路二：数论O(1)

  只需要判断这个数字模 9 之后的余数，若余 0 则返回 9，依据：x*100+y*10+z=x*99+y*9+x+y+z，x+y+z即为所求或下一次迭代的数。

class Solution {
public:
    int addDigits(int num) {
        if(num == 0) return 0;
        if(num % 9) return num % 9;
        else return 9;
        //return num % 9 ? num % 9 : 9;//写法二
        //return (num - 1) % 9 + 1;//写法三
    }
};