微信公众号手机网站开发成都网站建设制作公司
一、需求
- 给定一个非负整数
num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入:38输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
二、循环法、递归法
2.1 思路分析
- 题目既然提到了循环与递归，可以尝试着用这两种方法先解决；
2.2 循环法代码实现
class Solution {public int addDigits(int num) {int sum = 0;while(true) {sum = 0;while(num != 0) {int mod = num % 10;sum += mod;num = num / 10;}if(sum < 10) {//若这里用return代替break，则编译不会通过break;}num = sum;}return sum;}
}2.3 递归法代码实现
class Solution {//该方法作用是返回num各位之和public int addDigits(int num) {if(num < 10) return num;int sum = 0;while(num != 0) {int mod = num % 10;sum += mod;num = num / 10;}return addDigits(sum);}
}三、数学方法
3.1 思路分析
- 在数学上有个概念叫做树根，其含义就如题目描述的那样，每个自然数都有其对应的树根，本题的意思就是求正整数 n 的树根；
- 要求树根的规律：①n不是9的倍数，树根就是 n mod 9；②n是9的倍数，树根就是9；
- 为了方便计算，根据----Excel表列名称的思路：https://blog.csdn.net/Sruggle/article/details/113698482，设
，a表示 n 中含有多少个9，x是n对应的树根，若等式两边直接对 9 求余，则 x 的范围只有 1~8，因此我们考虑在等式两边减1，得到
，这样等式两边对 9 求余后，x -1 的范围为 0~8 ，从而 x 的范围为 1~9；
3.2 代码实现
class Solution {public int addDigits(int num) {return (num - 1) % 9 + 1;}
}3.3 复杂度分析
- 时间复杂度为O(1)；
- 空间复杂度为O(1)；
四、学习地址
作者：windliang
链接：https://leetcode-cn.com/problems/add-digits/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-7/