首页 > 其他 > 详细

LeetCode 258. 各位相加

时间:2021-01-31 11:39:21      阅读:20      评论:0      收藏:0      [点我收藏+]

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

 

LeetCode 258. 各位相加

原文:https://www.cnblogs.com/meteorrain/p/14351798.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!