LeetCode #258. Add Digits

593 0 0

作者:NemoWangCN

题目描述：

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?

Hint:A naive implementation of the above process is trivial. Could you come up with other methods?

题目大意：

给定一个非负整数num，重复地将其每位数字相加，直到结果只有一位数为止。
例如：
给定 num = 38，过程像这样：3 + 8 = 11, 1 + 1 = 2。因为2只有一位，返回之。
进一步思考：
你可以不用循环，在O(1)运行时间内完成题目吗？
提示：
一个直观的解法就是模拟上述过程。你可以想到别的方法吗？
结果一共有多少种可能性？
它们是周期性出现的还是随机出现的？

解题思路：

观察法
根据提示，由于结果只有一位数，因此其可能的数字为0 - 9
使用方法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 {
2 public:
3     int addDigits(int num) {
4         return (num-1)%9+1;
5     }
6 }

内容来源于网络如有侵权请私信删除

标签： C++ CPP C++语言开发 LeetCode

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

LeetCode #258. Add Digits