【LeetCode】#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?

Hint:
1.A naive implementation of the above process is trivial. Could you come up with other methods?
2.What are all the possible results?
3.How do they occur, periodically or randomly?
4.You may find this Wikipedia article useful.

题目大意,给出一个非负整数,求解该整数各个数字的和,如果所得和大于9,则再对这个和的各个数字求和,直到相加的结果为一个小于10的整数。

(1)题目中example的思路是,利用对整数除以10求余和求整来解决,这也是Hint中所谓的trivial方法,代码如下:
解法一:

解法二:

(2)然而Follow up中要求算法的时间复杂度为O(1),那么上述解法显然不符合要求。根据Hint中提及的2,3点,我们知道所有可能的结果为1-9,那么它们出现的分布情况会是怎样的呢,如下所示,周期为9,对9求余是解题的关键。

解法三:

 

《【LeetCode】#258 Add Digits》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注