数的各位相加

作者: ringawho | 来源:发表于2020-03-26 15:56 被阅读0次

    今天做LeetCode的时候,发现这样一道题,是简单的题,不过有一点点奇特

    题目让将一个数字的各位相加,出来的结果如果不是个位数,那么就再次相加,直到结果是个位数,这个个位数就是题目的结果

    原题如下:

    题目

    最直接的想法是按照这个题意来,如果发现加出来的结果不是个位数,那就再加一遍,代码如下:

    class Solution {
        public int addDigits(int num) {
            while (num >= 10) {
                int sum = 0;
                while (num > 0) {
                    sum += num % 10;
                    num /= 10;
                }
                num = sum;
            }
            return num;
        }
    }
    

    但是它题目下面还有一个要求:不使用循环和递归,并且在O(1)时间内完成(它写的是Follow up,我当做是必须的要求)

    思考一下,应该是有什么规律,否则不可能实现这个要求的,所以写出了一部分数字,然后发现结果是1-9一直循环,所以将修改了代码:

    class Solution {
        public int addDigits(int num) {
            if (num < 10)
                return num;
            num = num % 9;
            return num == 0? 9: num;
        }
    }
    

    提交了之后是正确的,但是我自己现在解释不了这个代码,所以还要再仔细研究一下这个规律

    考虑两位数[10, 100),他们各位数和的范围是1-18,假设它们都需要两遍和,第一遍数字范围1-18,第二遍变为1-9

    第一遍:

    每增加一个数,和也会增加1,假设sum(x)是x各位数的和,那么这时候sum(x+1) = sum(x)+1

    较为特殊的是39到40,前者39 => 12, 后者40 => 4,其实是个位数减9,十位数加1,那么它们的各位和符合:sum(x+1) = sum(x) - 9 + 1

    综合来说,第一遍有sum(x+1) = sum(x) + 1或者是sum(x+1) = sum(x) - 9 + 1两种情况

    第二遍:

    [1-18]这个范围内sum(x) = x % 9(当值为0的时候应该取值为9)成立

    这样的话对于两位数sum(x+1) = (sum(x)+1) % 9或者是sum(x+1) = (sum(x)+1-9) % 9,对于后边这个式子,-9可以省略掉,所以合并之后就是

    sum(x+1) = (sum(x) + 1) % 9 (当结果为0时,取值为9)

    这是两位数的情况,三位数的话第一遍和的结果范围变为[1, 27],第二遍范围[1, 18],第三遍[1, 9]
    ...
    12位,范围为[1, 108],第二遍范围[1, 18],第三遍[1, 9]
    ...

    最终可以得出sum(x+1) = (sum(x) + 1) % 9 (当结果为0时,取值为9)可以一直成立下去

    那么sum(x) = x % 9(结果为0时,取9)就是成立的,这就是我第二段代码的原理

    相关文章

      网友评论

        本文标题:数的各位相加

        本文链接:https://www.haomeiwen.com/subject/lelcuhtx.html