LeetCode - 算法

Swift - LeetCode - 各位相加

2022-08-25  本文已影响0人  晨曦的简书

题目

给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。返回这个结果。

示例 1:

  • 输入: num = 38
  • 输出: 2
  • 解释: 各位相加的过程为:
    38 --> 3 + 8 --> 11
    11 --> 1 + 1 --> 2
    由于 2 是一位数,所以返回 2

示例 2:

  • 输入: num = 0
  • 输出: 0

前言

这道题的本质是计算自然数 \textit{num} 的数根。

数根又称数字根(\text{Digital root}),是自然数的一种性质,每个自然数都有一个数根。对于给定的自然数,反复将各个位上的数字相加,直到结果为一位数,则该一位数即为原自然数的数根。

计算数根的最直观的方法是模拟计算各位相加的过程,直到剩下的数字是一位数。利用自然数的性质,则能在 O(1) 的时间内计算数根。

方法一:模拟

思路及解法

最直观的方法是模拟各位相加的过程,直到剩下的数字是一位数。

计算一个整数的各位相加的做法是,每次计算当前整数除以 10 的余数得到最低位数,将最低位数加到总和中,然后将当前整数除以 10。重复上述操作直到当前整数变成 0,此时的总和即为原整数各位相加的结果。

代码

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
    }
}

复杂度分析

方法二:数学

思路及解法

假设整数 \textit{num} 的十进制表示有 n 位,从最低位到最高位依次是 a_0a_{n - 1},则 \textit{num} 可以写成如下形式:

\begin{aligned} \textit{num} &= \sum_{i = 0}^{n - 1} a_i \times 10^i \\ &= \sum_{i = 0}^{n - 1} a_i \times (10^i - 1 + 1) \\ &= \sum_{i = 0}^{n - 1} a_i \times (10^i - 1) + \sum_{i = 0}^{n - 1} a_i \end{aligned}

i = 0 时,10^i - 1 = 09 的倍数;当 i 是正整数时,10^i - 1 是由 i9 组成的整数,也是 9 的倍数。因此对于任意非负整数 i10^i - 1 都是 9 的倍数。由此可得 \textit{num} 与其各位相加的结果模 9 同余。重复计算各位相加的结果直到结果为一位数时,该一位数即为 \textit{num} 的数根,\textit{num} 与其数根模 9 同余。

我们对 \textit{num} 分类讨论:

细节

根据上述分析可知,当 \textit{num} > 0 时,其数根的结果在范围 [1, 9] 内,因此可以想到计算 \textit{num} - 1 除以 9 的余数然后加 1。由于当 \textit{num} > 0 时,\textit{num} - 1 \ge 0,非负数除以 9 的余数一定也是非负数,因此计算 \textit{num} - 1 除以 9 的余数然后加 1 的结果是正确的。

\textit{num} = 0 时,\textit{num} - 1 = -1 < 0,负数对 9 取余或取模的结果的正负在不同语言中有所不同。

代码

class Solution {
    func addDigits(_ num: Int) -> Int {
        return (num - 1) % 9 + 1
    }
}

复杂度分析

上一篇 下一篇

猜你喜欢

热点阅读