題目
給定一個(gè)非負(fù)整數(shù) num，反復(fù)將各個(gè)位上的數(shù)字相加，直到結(jié)果為一位數(shù)。返回這個(gè)結(jié)果。
示例 1：
- 輸入：
num = 38- 輸出：
2- 解釋： 各位相加的過(guò)程為：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于2是一位數(shù)，所以返回2。
示例 2：
- 輸入：
num = 0- 輸出：
0
前言
這道題的本質(zhì)是計(jì)算自然數(shù) 的數(shù)根。
數(shù)根又稱數(shù)字根（），是自然數(shù)的一種性質(zhì)，每個(gè)自然數(shù)都有一個(gè)數(shù)根。對(duì)于給定的自然數(shù)，反復(fù)將各個(gè)位上的數(shù)字相加，直到結(jié)果為一位數(shù)，則該一位數(shù)即為原自然數(shù)的數(shù)根。
計(jì)算數(shù)根的最直觀的方法是模擬計(jì)算各位相加的過(guò)程，直到剩下的數(shù)字是一位數(shù)。利用自然數(shù)的性質(zhì)，則能在 的時(shí)間內(nèi)計(jì)算數(shù)根。
方法一：模擬
思路及解法
最直觀的方法是模擬各位相加的過(guò)程，直到剩下的數(shù)字是一位數(shù)。
計(jì)算一個(gè)整數(shù)的各位相加的做法是，每次計(jì)算當(dāng)前整數(shù)除以 10 的余數(shù)得到最低位數(shù)，將最低位數(shù)加到總和中，然后將當(dāng)前整數(shù)除以 10。重復(fù)上述操作直到當(dāng)前整數(shù)變成 0，此時(shí)的總和即為原整數(shù)各位相加的結(jié)果。
代碼
class Solution {
func addDigits(_ num: Int) -> Int {
var num = num
while num >= 10 {
var sum: Int = 0
while num > 0 {
sum += num % 10
num /= 10
}
num = sum
}
return num
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
，其中
是給定的整數(shù)。對(duì)于
，因此對(duì)于
，對(duì)于任意兩位數(shù)最多只需要計(jì)算兩次各位相加的結(jié)果即可得到一位數(shù)。
空間復(fù)雜度：
。
方法二：數(shù)學(xué)
思路及解法
假設(shè)整數(shù) 的十進(jìn)制表示有
位，從最低位到最高位依次是
到
，則
可以寫成如下形式：
當(dāng) 時(shí)，
是
的倍數(shù)；當(dāng)
是正整數(shù)時(shí)，
是由
位
組成的整數(shù)，也是
的倍數(shù)。因此對(duì)于任意非負(fù)整數(shù)
，
都是
的倍數(shù)。由此可得
與其各位相加的結(jié)果模
同余。重復(fù)計(jì)算各位相加的結(jié)果直到結(jié)果為一位數(shù)時(shí)，該一位數(shù)即為
的數(shù)根，
與其數(shù)根模
同余。
我們對(duì) 分類討論：
-
不是
的倍數(shù)時(shí)，其數(shù)根即為
-
- 如果
，則其數(shù)根是
；
- 如果
，則各位相加的結(jié)果大于
- 如果
細(xì)節(jié)
根據(jù)上述分析可知，當(dāng) 時(shí)，其數(shù)根的結(jié)果在范圍
[1, 9] 內(nèi)，因此可以想到計(jì)算 除以
的余數(shù)然后加
。由于當(dāng)
時(shí)，
，非負(fù)數(shù)除以
的余數(shù)一定也是非負(fù)數(shù)，因此計(jì)算
除以
的余數(shù)然后加
的結(jié)果是正確的。
當(dāng) 時(shí)，
，負(fù)數(shù)對(duì)
取余或取模的結(jié)果的正負(fù)在不同語(yǔ)言中有所不同。
對(duì)于取余的語(yǔ)言，結(jié)果的正負(fù)和左操作數(shù)相同，則
對(duì)
，加
后得到結(jié)果
對(duì)于取模的語(yǔ)言，結(jié)果的正負(fù)和右操作數(shù)相同，則
，加
代碼
class Solution {
func addDigits(_ num: Int) -> Int {
return (num - 1) % 9 + 1
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
空間復(fù)雜度：
