给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
思路：
正常解法，因为题目没有给任何长度限制，也不知道后端是什么情况，姑且用大整数进行存储吧...所以，这一题我就直接用大整数存储，然后不断进行遍历求和，直到大整数的长度为1停止，还挺简单的~
O(1)解法：我觉得吧，正常情况下除非从0开始写个一二十个数，才能找到规律，找到规律之后当然就简单了，就是这个数如果能被9整除，那么和必为9(0除外，0的和就是0)，否则为这个数除9之后的余数，这是看的大佬的解答，反正我是找不到T-T。
代码：
正常解：
1 struct bign 2 { 3 int d[1010]; 4 int len; 5 bign() 6 { 7 memset(d,0,sizeof(d)); 8 len=0; 9 } 10 }; 11 12 bign change(int a) 13 { 14 bign b; 15 do 16 { 17 b.d[b.len++]=a%10+‘0‘; 18 a=a/10; 19 } 20 while(a!=0); 21 return b; 22 } 23 24 class Solution { 25 public: 26 int addDigits(int num) { 27 bign a=change(num); 28 while(a.len!=1) 29 { 30 bign b; 31 //进行大整数自加 32 int carry=0; 33 for(int i=0;i<a.len;++i) 34 { 35 carry+=a.d[i]-‘0‘; 36 } 37 //处理进位 38 b.d[b.len++]=carry%10+‘0‘; 39 carry/=10; 40 while(carry!=0) 41 { 42 b.d[b.len++]=carry%10+‘0‘; 43 carry/=10; 44 } 45 //将结构体b复制给a 46 for(int i=0;i<b.len;++i) 47 { 48 a.d[i]=b.d[i]; 49 } 50 a.len=b.len; 51 } 52 return a.d[0]-‘0‘; 53 } 54 };
O(1)解：
1 class Solution { 2 public: 3 int addDigits(int num) { 4 if(num==0) 5 return 0; 6 if(num%9==0) 7 return 9; 8 return num%9; 9 } 10 };
原文：https://www.cnblogs.com/meteorrain/p/14351798.html