用 Swift 刷 LeetCode No.258 - Add

转自我的 blog: 用 Swift 刷 LeetCode No.258 - Add Digits

用 Swift 刷 LeetCode 的第四弹，Add Digits。

add_digits.png

题目 Easy 级别，也是目前我第一道一遍写成就通过的题目（无语法错误无错误无超时，爽爽爽）！

通过的代码如下，还用了一下 Array 的 reduce：

class Solution {
  func addDigits(num: Int) -> Int {
        if num < 10 {
            return num
        }
        var numbers = [Int]()
        var n = num
        let base = 10
        while n > 0 {
            numbers.append(n % base)
            n /= base
        }
        let sum = numbers.reduce(0) {
            $0 + $1
        }
        return addDigits(sum)
    }

}

然而，这个题目还让你想想有没有不用任何循环和递归的解法，也就是 O(1) 的复杂度。
这个要求对我来说就是超纲题了啊，O(1) 的话那不就是判断＋赋值了吗……
结果这个题的 O(1) 解法就是个数学题，这个是有公式的（wiki）。求的解是个叫 Digital Root 的东西，维基百科里面有求解详细的证明和过程（我是懒得看了）。就目前遇到的两个题来说，貌似 O(1) 解法的题都是靠数学公式才可以。