[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.

题目大意:

(手动翻译)给你一个非负整数 num ,重复相加它的所有整数直到结果只有个位数。

比如说:

给你一个数字 38 ,这个过程就是:3 + 8 = 11 , 1 + 1 = 2 ,直到2是一位数,将它返回。

    接下来:

你能不用循环/递归,用O(1)去解决这个问题吗?

    提示:

1. 重复以上过程的天真解法是微不足道的。你能想出其他的解决办法吗?

2. 所有可能的结果是什么?

3. 他们是如何产生的,是周期性的还是随机的?

4. 你可能会觉得这个 维基百科文章 很有用。


 

我做事向来比较急躁,总是想着马上得到答案。但在难度较高的题目面前,这个缺点会害死我。

没错,有网站,干嘛不看?赶紧点进去看呀。

“(引用)

Significance and formula of the digital root[edit]

It helps to see the digital root of a positive integer as the position it holds with respect to the largest multiple of 9 less than it. For example, the digital root of 11 is 2, which means that 11 is the second number after 9. Likewise, the digital root of 2035 is 1, which means that 2035 − 1 is a multiple of 9. If a number produces a digital root of exactly 9, then the number is a multiple of 9.

With this in mind the digital root of a positive integer may be defined by using floor function [x], as

(手动翻译,有问题请指出)

        根数字的意义和公式

观察得到对于一个正整数的根数字所在的位置最大不超过 9 是十分有帮助的。(额求英语能手救我!)比如说:11 的根数字是 2 ,同时意味着 11 是 9 之后的第二个数字。同样的,2035 的根数字是 1 ,同时意味着 2035 – 1 是 9 的倍数。如果一个数字的根数字正好是 9 ,那么这个数字也是 9 的倍数。(英语能手们,这边翻译成被 9 整除会不会好一些?)

带着这样的思路,那么 n 的根数字可能用上取整函数 [x] 写出来,即:

行啊那就结束了。直接把它敲进OJ里肯定OK了。

然后就通过了。两手一摊,谁叫你连维基百科的链接都上好给我抄呢。

不过这题给我的启发是,通过特殊情况反推一般情况的思路。提干中给出 11 为 2。其实如果细心想想,也能够猜到 11 与 9 只差 2 。而得到 9 的思路是,这个根数字一定是在 0 – 9 之间。若是能想出这一步,问题就会变得简单。

所以该问题的第 2 、3 点提示也就是在引导答题人往找寻规律的方向去思考,而不要局限于最常规的算法。