LeetCode 258. 各位相加

Categories:

题目描述
思路分析
1. 解法一：数字根公式（推荐）
2. 解法二：模拟迭代
相似题目

题目描述

✅ 258. 各位相加

思路分析

解法一：数字根公式（推荐）

核心思路：

各位相加是求数字根（Digital Root）的过程，最终结果一定在 1～9 之间（0 除外）

数学结论：对于正整数 n，数字根等于 1 + (n - 1) % 9

当 n = 0 时直接返回 0；对其他数，利用模 9 的周期性可以 O(1) 得出答案

推导：每次将各位相加，相当于对 9 取模后的余数（当余数为 0 时结果为 9）

复杂度分析：

时间复杂度：O(1)，直接计算，无循环

空间复杂度：O(1)，只用常数额外空间

class Solution {
  public int addDigits(int num) {
    if (num == 0) {
      return 0;
    }

    // 利用数字根公式：1 + (num - 1) % 9
    return 1 + (num - 1) % 9;
  }
}

func addDigits(num int) int {
    if num == 0 {
        return 0
    }

    // 利用数字根公式：1 + (num-1) % 9
    return 1 + (num-1)%9
}

解法二：模拟迭代

核心思路：

循环对整数的各位求和，直到结果为一位数

每轮将 num 的各位相加得到新 num，直到 num < 10

复杂度分析：

时间复杂度：O(log n)，每次迭代位数减少

空间复杂度：O(1)

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

func addDigits(num int) int {
    // 循环直到结果为一位数
    for num >= 10 {
        sum := 0

        for num > 0 {
            sum += num % 10
            num /= 10
        }

        num = sum
    }

    return num
}

相似题目

题目	难度	考察点
202. 快乐数	简单	数学、哈希表
263. 丑数	简单	数学
264. 丑数 II	中等	动态规划、堆
319. 灯泡开关	中等	数学
342. 4 的幂	简单	数学、位运算
412. Fizz Buzz	简单	数学、模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/66554720