Leetcode258 各位相加

每天一道leetcode,之前写完的题解都放在OneNote上,想来总觉得有些不方便还容易懈怠,还是写在这里吧。^^
先把简单题给刷完 那么开始吧

题目描述

file

我的解法:

很自然的想法就是把数字转化成字符串,然后逐个处理,判断len(tmp)<=1

class Solution:
    def addDigits(self, num: int) -&gt; int:
        num=str(num)
        while(len(num)&gt;1):
            tmp=0
            for letter in num:
                tmp+=int(letter)
            tmp=str(tmp)
            num=tmp
        return int(num)

O(1)解法:

class Solution:
    def addDigits(self, num: int) -&gt; int:
        if num &gt; 9:
            num = num % 9
            if num == 0:
                return 9
        return num

对9取余即为题解的原理:
假设对123求各位数字之和,有123 = 100x1 + 10x2 + 1x3
file
于是各位数之和F就是
F(123) = (100 - 99) + (10 - 9) * 2 + 3 = 123 - 99 * 1 - 9 * 2 + 3
即10堆去掉9,100堆去掉99,1000堆去掉999,即为各位数之和
于是9就是这么来的
并没有严格证明/推导, 理解个意思就行