力扣打卡第一天258. 各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

示例 1:

输入: num = 38
输出: 2 
解释: 各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。

示例 1:

输入: num = 0
输出: 0

最简单的办法是可以采用递归，但可能会造成溢出。递归代码如下：

class Solution {

    public int addDigits(int num) {

        if(num<10){

          return num;

         }

        int next=0;

        while(num>=10){

            next=next+num%10;

            num=num/10;

        }

        num=next+num;

        return addDigits(int num);

    }

}

也可以采用while循环，循环代码如下：

class Solution {

    public int addDigits(int num) {

        while(num>=10){

        int next=0;

        while(num>=10){

            next=next+num%10;

            num=num/10;

        }

        num=next+num;

        }

        return num;

    }

}

上述两种办法的时间复杂度都比较高，下面分析是否能将时间复杂的控制在 O(1)。

参考力扣上的大神代码（太强了）

除了传统的单纯循环，还可以找规律。假如一个三位数'abc'，其值大小为s1 = 100 * a + 10 * b + 1 * c，经过一次各位相加后，变为s2 = a + b + c，减小的差值为(s1 -s2) = 99 * a + 9 * b，差值可以被9整除，每一个循环都这样，缩小了9的倍数。当num小于9，即只有一位时，直接返回num，大于9时，如果能被9整除，则返回9（因为不可能返回0也不可能返回两位数及以上的值），如果不能被整除，就返回被9除的余数。

class Solution:
    def addDigits(self, num: int) -> int:
        if num > 9:
            num = num % 9
            if num == 0:
                return 9
        return num

最后

以上就是落后小蘑菇为你收集整理的力扣打卡第一天258. 各位相加的全部内容，希望文章能够帮你解决力扣打卡第一天258. 各位相加所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。