江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第258题：各位相加

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

题目描述

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

输入: num = 0
输出: 0

提示

  • 0 <= num <= 2^31 - 1

进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

解题思路

方法一：模拟法

最直观的解法是按照题意进行模拟。我们不断地将数字的各位相加，直到结果为一位数（即小于10）为止。

关键点

  • 循环检查num是否大于等于10
  • 在内层循环中计算所有位的和
  • 将和赋值给num，继续外层循环，直到num小于10

具体步骤

  1. 如果num小于10，直接返回num
  2. 否则，循环执行以下操作：
    • 计算num各位数字的和
    • 将和赋值给num
    • 检查num是否小于10，如果是则返回结果

复杂度分析

  • 时间复杂度：O(log num)，每次循环num会变为num的数字和，通常会减小到原来的1/10或更小
  • 空间复杂度：O(1)，只使用了常数额外空间

方法二：数学方法

这个问题其实有一个数学解法，叫做“数字根”（Digital Root）。对于非零数字，数字根就是num对9取余的结果，当num是9的倍数时，数字根为9。

关键点

  • 数字根的计算公式：(num - 1) % 9 + 1，当num不为0时
  • 当num为0时，数字根为0

复杂度分析

  • 时间复杂度：O(1)，只需要一次计算
  • 空间复杂度：O(1)，只使用了常数额外空间

图解思路

方法一：模拟过程示例

以示例1中的数字38为例：

步骤 当前num 操作 结果
1 38 38 >= 10，计算3+8 11
2 11 11 >= 10，计算1+1 2
3 2 2 < 10,结束循环 2

方法二：数学推导

数字根具有周期性：

原始数字 1 2 3 4 5 6 7 8 9 10 11 12 …
数字根 1 2 3 4 5 6 7 8 9 1 2 3 …

可以看出，除了0以外，数字根是1到9循环出现的，周期为9。

对于数字38：

  • (38 - 1) % 9 + 1 = 37 % 9 + 1 = 1 + 1 = 2

这与通过模拟得到的结果一致。

代码实现

C# 实现

public 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;
    }
    
    // 方法二：数学方法
    public int AddDigits2(int num) {
        if (num == 0) return 0;
        return (num - 1) % 9 + 1;
    }
}

Python 实现

class Solution:
    # 方法一：模拟法
    def addDigits(self, num: int) -> int:
        while num >= 10:
            sum = 0
            while num > 0:
                sum += num % 10
                num //= 10
            num = sum
        return num
    
    # 方法二：数学方法
    def addDigits2(self, num: int) -> int:
        if num == 0:
            return 0
        return (num - 1) % 9 + 1

C++ 实现

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;
    }
    
    // 方法二：数学方法
    int addDigits2(int num) {
        if (num == 0) return 0;
        return (num - 1) % 9 + 1;
    }
};

执行结果

C# 实现

  • 方法一（模拟法）
    • 执行用时：28 ms
    • 内存消耗：27.2 MB
  • 方法二（数学方法）
    • 执行用时：20 ms
    • 内存消耗：27.1 MB

Python 实现

  • 方法一（模拟法）
    • 执行用时：40 ms
    • 内存消耗：16.2 MB
  • 方法二（数学方法）
    • 执行用时：36 ms
    • 内存消耗：16.3 MB

C++ 实现

  • 方法一（模拟法）
    • 执行用时：0 ms
    • 内存消耗：6.1 MB
  • 方法二（数学方法）
    • 执行用时：0 ms
    • 内存消耗：6.0 MB

性能对比

语言 方法 执行用时 内存消耗 特点
C# 模拟法 28 ms 27.2 MB 直观易懂，但性能较差
C# 数学方法 20 ms 27.1 MB 性能更佳，实现简单
Python 模拟法 40 ms 16.2 MB 代码简洁，但较慢
Python 数学方法 36 ms 16.3 MB 性能稍好，一行代码解决
C++ 模拟法 0 ms 6.1 MB 性能优异
C++ 数学方法 0 ms 6.0 MB 性能最佳，内存占用最小

代码亮点

  1. 🎯 数学方法提供了一种不需要循环或递归的O(1)解法
  2. 💡 两种方法都处理了边界情况（如num为0的情况）
  3. 🔍 模拟法直观体现了题目要求的过程
  4. 🎨 代码结构清晰，逻辑易于理解

常见错误分析

  1. 🚫 忘记处理num为0的特殊情况
  2. 🚫 在计算数字根时使用错误的公式
  3. 🚫 在模拟过程中没有正确更新num的值
  4. 🚫 使用递归实现时没有考虑到栈溢出的可能性

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
模拟法 O(log num) O(1) 直观易懂，容易实现 性能较差，需要多次循环
数学方法 O(1) O(1) 性能最佳，一步到位 需要理解数字根的数学性质
递归法 O(log num) O(log num) 代码简洁 可能导致栈溢出

相关题目