TNotes.leetcode

Appearance

0258. 各位相加【简单】

0258. 各位相加【简单】 ​

1. 📝 题目描述 ​

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

示例 1：

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

示例 2：

txt
输入: num = 0
输出: 0

提示：

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

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

题目分析

  • 这道题要求将一个非负整数的各位数字不断相加，直到结果为一位数，返回这个一位数。
  • 例如：38 → 3+8=11 → 1+1=2，返回 2。
  • 我们可以使用多种方法来解决这个问题：
    1. 模拟法：循环计算各位数字之和直到结果为一位数
    2. 数学法：利用数字根的数学性质直接计算结果
      • 这种解法需要知道数字根的求解公式

2. 🎯 s.1 - 模拟法（循环） ​

js
/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  while (num >= 10) {
    let sum = 0
    // 计算各位数字之和
    while (num > 0) {
      sum += num % 10
      num = Math.floor(num / 10)
    }
    num = sum
  }
  return num
}
  • 时间复杂度：O(log⁡n)，每次循环数字位数减少
  • 空间复杂度：O(1)

3. 🎯 s.2 - 模拟法（递归） ​

js
/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  // 如果是一位数，直接返回
  if (num < 10) return num

  let sum = 0
  // 计算各位数字之和
  while (num > 0) {
    sum += num % 10
    num = Math.floor(num / 10)
  }

  // 递归处理和
  return addDigits(sum)
}
  • 时间复杂度：O(log⁡n)
  • 空间复杂度：O(log⁡n)，递归调用栈

4. 🎯 s.3 - 数学规律（数字根算法） ​

js
/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  // 数字根公式：
  // 如果 num 为 0，结果为 0
  // 如果 num 能被 9 整除且不为 0，结果为 9
  // 否则结果为 num % 9
  if (num === 0) return 0
  return num % 9 === 0 ? 9 : num % 9
}
js
/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  // 数字根的另一种表达方式
  return 1 + ((num - 1) % 9)
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)
  • 数字根
    • 定义：数根（又称数字根）是正整数的一种属性，指通过重复计算各位数字之和直至结果为个位数的值。
    • 性质：
      • img
  • 核心公式的简单推导流程：
txt
公式：
num 的根 = 1 + ((num - 1) mod 9)

公式的详细推导过程，在笔记中不作记录。

下面是根据题目已知条件的倒推思考流程，帮忙理清公式是怎么来的：
1️⃣ 385 的根 = (3 + 8 + 5) 的根
2️⃣ 385 的根 = (3 * 100 + 8 * 10 + 5) 的根
3️⃣ (3 + 8 + 5) 的根 = (3 * 100 + 8 * 10 + 5) 的根

1️⃣ 成立能推导出 2️⃣ 成立
3️⃣ 也就是 1️⃣ 2️⃣ 相等可以根据题目描述推导出来

3️⃣ 要成立，可以通过 mod 9 来实现，因为 10^k mod 9 = 1

模运算基本性质：(A + B) mod m = [(A mod m) + (B mod m)] mod m

385 mod 9
= (5×1 + 8×10 + 3×100) mod 9
= (5×1 + 8×1 + 3×1) mod 9   ← 因为 10ᵏ ≡ 1 (mod 9)
= (5 + 8 + 3) mod 9
= 16 mod 9
= 7

结论：num 的根 = num mod 9
num 的数字根其实就是 num 对 9 取模的结果。

问题：
如果直接用 num mod 9，结果可能是 0。
但数字根的范围是 1~9，只有 num=0 时才允许结果是 0。

可以引入了一个“偏移”（减 1）来解决此问题：
num 的根 = 1 + ((num - 1) mod 9)
公式中的减 1 是为了把「余数为 0」的情况挪到「9」去
这样就能保证数字根永远落在 1 ∼ 9 而不会出现错误的 0（除非输入本身就是 0）

再思考：偏移为什么是 -1，不是 -2、-3 呢？
很简单，num mod 9 的取值范围是 0 ～ 8

倘若将公式改为：
num 的根 = 2 + ((num - 2) mod 9)

那么最终的结果区间将会是 2 ～ 10
显然这是不满足题目要求的！

5. 🔗 引用 ​

Discussions