题目:
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?

思路:
按照提示,去 wiki 看了下这个算法 Digital root,排列一部分数据,得出原始数-最大9的整数倍,即为目标值。算法复杂度 O(1)!!!!!!

代码:

class Solution
{
public:

int addDigits(int num) 
{
    if( num <= 9 )
    {
        return num;
    }
    int nTargetNum = num / 9;
    int nResult = num - nTargetNum * 9;
    return nResult > 0 ? nResult : 9;
}

};
总结:
1、思路很重要,看到题目的竟然想到的是记录每个数位上的值,这样算法复杂度不知道要高多少倍了
2、临界值!没有无bug的程序,只有未找到的边界值,多想想边界值。
3、提交了3次才通过,很惭愧!

标签: none

添加新评论