我是小小强，这是我的第7篇原创文章，阅读需要大约10分钟。
题目
LintCode:各位相加
描述
给出一个非负整数 num，反复的将所有位上的数字相加，直到得到一个一位的整数。
样例
给出 num = 38。
相加的过程如下：3 + 8 = 11，1 + 1 = 2。因为 2 只剩下一个数字，所以返回2。
思路
题目要求各位相加，想当然的思路就是每次除于10，然后余数相加，直到无法被10整除，然后再把最后的余数加起来。
实现
递归实现
- java实现
public class Solution {
/**
* @param num a non-negative integer
* @return one digit
*/
public int addDigits(int num) {
// Write your code here
int sum = 0;
while(num / 10 >= 1){
sum += num % 10;
num /= 10;
}
sum += num % 10;
if (sum >= 10)
sum = addDigits(sum);
return sum;
}
}
- 结果分析
结果：结果通过了LintCode的要求。
分析：这种实现比较好理解，但是实现起来却没什么巧妙之处。并且时间慢。
其它优化参考
LintCode:569 各位相加
LeetCode discuss
数学原理
https://en.wikipedia.org/wiki/Digital_root
[Step 1]:
438 == 40*10 +3*10 +8 ;
4+3+8 == 4*(10%9)*(10%9)+3*(10%9)+8%9= 15 ;
[Step 2]:
15 == 1*10 + 5 ;
1+5 == 1*(10%9)+5%9= 6 ;
[So we can see]:
ab%9%9%9==ab%9;
just return num%9; and don't forget num==0 or num==9
优秀代码
public class Solution {
public int addDigits(int num) {
return num==0?0:(num%9==0?9:(num%9));
}
}
