给定一个非负整数 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