题目描述

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

示例

示例 1:

输入: num = 38
输出: 2
解释: 各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2

由于 2 是一位数，所以返回 2。

示例 2:

输入: num = 0
输出: 0

提示：

0 <= num <= 2312^{31}231 - 1

进阶：

你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

解题思路

看题目描述看的我蒙了，示例看完就清晰多了。

给我的启发是，以后自己撸文章也尽量多给一些示例。这样能让读者清晰。

这道题的本质是计算自然数的数根。

树根的概念是这样的：树根是自然数的一种性质，每个自然数都有一个数根。对于给定的自然数，反复将各个位上的数字相加，直到结果为一位数，则该一位数就是原自然数的数根。

清楚了这个概念我们就可以利用解树根的方式来解这道题了。

我的思路是模拟各个位上数字相加的过程，直到剩下的数字是一位数。

即：每次计算当前整数除以10的余数得到最低位数，将最低位数加到总和中，然后再将当前整数除以 10。重复这个思路的操作，直到当前整数变成0的时候，这时的总和就是原整数各位相加的结果了。

AC代码

func addDigits(num int) int {
    for num >= 10 {
        sum := 0
        for ; num > 0; num /= 10 {
            sum += num % 10
        }
        num = sum
    }
    return num
}

运行结果

总结

了解基础概念之后再解题思路就清晰多了，在刷题的过程中有学到了不少新概念。