258. Add Digits
Given a non-negative integer num
, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38
, the process is like: 3 + 8 = 11
, 1 + 1 = 2
. Since 2
has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
题目大意:
给定一个非负整数num,重复地将其每位数字相加,直到结果只有一位数为止。
例如:
给定 num = 38,过程像这样:3 + 8 = 11, 1 + 1 = 2。因为2只有一位,返回之。
进一步思考:
你可以不用循环,在O(1)运行时间内完成题目吗?
解题方法:
1.模拟上述方法(递归)。
2.观察法。
使用方法I的代码循环输出0 - 19的运行结果:
in out in out
0 0 10 1
1 1 11 2
2 2 12 3
3 3 13 4
4 4 14 5
5 5 15 6
6 6 16 7
7 7 17 8
8 8 18 9
9 9 19 1
可以发现输出与输入的关系为:
out = (in - 1) % 9 + 1
注意事项:
C++代码:
1.递归:
class Solution
{
public:
int addDigits(int num)
{
int tmp=num/+num%;
if(tmp<)
{
return tmp;
}
else
{
num=tmp;
tmp=addDigits(num);
}
return tmp;
}
};
2.观察法:
class Solution
{
public:
int addDigits(int num)
{
if (num == )
return ;
return (num - ) % + ;
}
};