这是悦乐书的第199次更新，第207篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第63题（顺位题号是258）。给定非负整数num，重复添加其所有数字，直到结果只有一位数。例如：
输入：38
输出：2
说明：过程如下：3 + 8 = 11,1 + 1 = 2。由于2只有一位数，所以请将其返回。
跟进：你可以在O（1）运行时间内没有任何循环/递归的情况下执行此操作吗？
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
特殊情况：如果num小于10，直接返回num即可。
正常情况：此解法是利用递归，因为每计算一次后得到的结果还是相同的问题。因为题目给定的是正整数，所以可以借助字符串来操作。先将num转为字符串，然后依次获取字符相加，得到每位数的和，然后继续调用自身。
public int addDigits(int num) {
if (num < 10) {
return num;
}
String str = num+"";
int sum = 0;
for (int i=0; i<str.length(); i++) {
sum += str.charAt(i)-'0';
}
return addDigits(sum);
}
03 第二种解法
特殊情况：如果num小于10，直接返回num即可。
正常情况：此解法是利用迭代，使用两层循环，外层判断大小，内层进行数据计算，先对10取余，再除以10，进入下一位接着计算，如果算到最后一位，跳出内层循环，此时还要加上对10取余的余数，因为内层循环只是做判断，然后将算出的和赋值给num，sum归为0，再开始下一次的循环。
public int addDigits2(int num) {
if (num < 10) {
return num;
}
int sum = 0;
while (num >= 10) {
while (num/10 != 0) {
sum += num%10;
num /= 10;
}
sum += num%10;
num = sum;
sum = 0;
}
return num;
}
04 第三种解法
可以先计算一部分数据，找找规律。
9 --> 9 --> 9%9=0 ？
10 --> 1 --> 10%9=1
13 --> 4 --> 13%9=4
18 --> 9 --> 18%9=0 ？
19 --> 1 --> 19%9=1
22 --> 4 --> 22%9=4
25 --> 7 --> 25%9=7
27 --> 9 --> 27%9=0 ？
29 --> 2 --> 29%9=2
33 --> 6 --> 33%9=6
36 --> 9 --> 36%9=0 ？
37 --> 1 --> 37%9=1
39 --> 3 --> 39%9=3
43 --> 7 --> 43%9=7
45 --> 9 --> 45%9=0 ？
46 --> 1 --> 46%9=1
49 --> 4 --> 49%9=4
通过上面这些数的计算，可以发现最后计算出的结果是有周期的，从1到9不断循环，并且除了9的倍数以外的数,其他的数都可以间接通过对9取余得到最后的结果，但是以9为倍数的整数，我们可以曲线救国，将原数减1后再对其取余，然后再把1补上。最后我们得到这样的公式：(num-1)%9 + 1。
public int addDigits3(int num) {
return (num-1)%9 + 1;
}
05 小结
算法专题目前已连续日更超过一个月，算法题文章63+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
