这是我参与11月更文挑战的第15天,活动详情查看:2021最后一次更文挑战。
题目描述:
258. 各位相加 - 力扣(LeetCode) (leetcode-cn.com)
给定一个非负整数 num
,反复将各个位上的数字相加,直到结果为一位数。
示例一
输入: 38
输出: 2
解释: 各位相加的过程为 : 3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。
复制代码
进阶:
你可以不使用循环或者递归,且在
时间复杂度内解决这个问题吗?
思路分析
数学
进阶要求我们
时间复杂度,那第一反应的遍历,递归等解法肯定就不符合题意了,一般这样的解法都是数学解法。
- 能够被9整除的整数,各位上的数字加起来也必然能被9整除,所以,连续累加起来,最终必然就是9。
- 不能被9整除的整数,各位上的数字加起来,结果对9取模,和初始数对9取模,是一样的,所以,连续累加起来,最终必然就是初始数对9取模。
AC代码
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
复制代码
总结
这种题,题解看似只有简单的一行,但是背后的数学才是解题的关键。
这个题解在数学中其实叫数字根,至于什么是数字根我就不解释了,这位老哥的回答很详细,大家可以参考参考。 详细通俗的思路分析,多解法 - 各位相加 - 力扣(LeetCode) (leetcode-cn.com),里面还有推导的过程,感兴趣的自行查阅。
参考
【Java】O(1)解法的个人理解 - 各位相加 - 力扣(LeetCode) (leetcode-cn.com)
近期评论