阅读量:6
🎁个人主页：我们的五年
🔍系列专栏：每日一练
🌷追光的人，终会万丈光芒
前言：
【LeetCode】真的是一个好网站呀，上面的题目的太经典了，提供的方法也很很多，非常值得推荐。
下面给大家带来一道经典题。
各位相加：
【LeetCode】链接：258. 各位相加 - 力扣（LeetCode）
🏝问题描述：
问题：
给定一个非负整数
num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。示例 1:
输入: num = 38 输出: 2 解释: 各位相加的过程为： 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 由于2是一位数，所以返回 2。示例 2:
输入: num = 0 输出: 0进阶：你可以不使用循环或者递归，在
O(1)时间复杂度内解决这个问题吗？
🏝解法一（模拟）：
第一步就是把每一个位数的数字相加，得到一个新的数，然后再把每一位的数相加，再得到一个新的数，最后等这个数小于10为止。
实现代码：
int addDigits(int num) {
while(num>=10)
{
int sum=0;
while(num)
{
sum+=num%10;
num/=10;
}
num=sum;
}
return num;
}
int addDigits(int num) { while(num>=10) { int sum=0; while(num) { sum+=num%10; num/=10; } num=sum; } return num; }🏝解法二（数学）：
题目末尾说了这样一句话：
进阶：你可以不使用循环或者递归，在
O(1)时间复杂度内解决这个问题吗？
上面的代码执行的：执行次数为肯定不是一个常数，所以时间复杂度为O(N)。
下面看一下这个公式：
后面这个公式：
=sum，就是每一个数字的和
然后，前面的（10^i-1）一定是9的倍数，然后我们左右两边都除以9，就可以这样，
num/9=0+sum1/9=0+sum2/9=……=k;
最后得到结果k就是最后的结果，但是，k的范围是0~8，但是当n>0时，结果应该是1~9.
（num-1）/9=(sum-1)/9=……=k-1
此时的k是0~8，然后加上1就是1~9,所以最后结果就是（n-1）%9+1；
当n等于0时，结果应该为0,（0-1）%9+1=-1+1=0.也是没有问题的
🏝取模和取余的区别：
【LeetCode】官方解释：
●对于取余的语言，结果的正负和左操作数相同，则 num−1\textit{num} - 1num−1 对 999 取余的结果为 −1-1−1，加 111 后得到结果 000，可以得到正确的结果；
●对于取模的语言，结果的正负和右操作数相同，则 num−1\textit{num} - 1num−1 对 999 取模的结果为 888，加 111 后得到结果 999，无法得到正确的结果，此时需要对 num=0\textit{num} = 0num=0 的情况专门做处理。
作者：力扣官方题解
链接：https://leetcode.cn/problems/add-digits/solutions/1301157/ge-wei-xiang-jia-by-leetcode-solution-u4kj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
也就是说：
取余：负数取余以后还是负数，正数取余还是正数。
取模：一个数对正数取模还是正数，一个数对负数取模就是负数。
