258. 各位相加
难度：简单
题目
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。
示例 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) 时间复杂度内解决这个问题吗？
个人题解
方法一：打表法
思路：
- 显然，由题目可知，这是一道找规律的题目
- 先编写不管复杂度的程序，将10000以下对应的的答案打印出来，观察规律
public class Main {
public static void main(String[] args) {
Main main = new Main();
for (int i = 0; i < 10000; i++) {
System.out.println(main.addDigits(i) + " " + i);
}
}
public int addDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num >= 10) {
sum += num % 10;
num /= 10;
}
num = sum + num;
}
return num;
}
}
观察输出，除了小于 10 的数，后面数字都是一直从 1~9 逐位递增，观察规律，当能被 9 整除时，对应答案是 9，否则是 除以9 的余数，则编写以下代码：
class Solution {
public int addDigits(int num) {
if (num < 10) {
return num;
}
return num % 9 == 0 ? 9 : num % 9;
}
}
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：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;
}
}
复杂度分析
- 时间复杂度：O(log num)
- 空间复杂度：O(1)
方法二：数学
从数学角度分析答题，题解字数很多，本人不想看，想看的可直接点击后面链接查看
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
作者：力扣官方题解
链接：https://leetcode.cn/problems/add-digits/solutions/1301157/ge-wei-xiang-jia-by-leetcode-solution-u4kj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
