LeetCode笔记:258.Add Digits
2023-03-15 23:22:12 时间
问题:
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. Follow up: Could you do it without any loop/recursion in O(1) runtime?
大意:
给一个非负数,重复地加其中的数字知道最后只有一个数字。 比如说: 给出数字38,过程类似于:3+8=11,1+1=2.直到2只有一个数字了,就返回它。 继续: 你能不能不用任何循环、递归来在O(1)的时间复杂度中完成它?
思路一:
首先想到的就是循环,对于一个数字,循环将其除以10的余数加起来,直到其是个位数。加完一次后判断是不是没数字了,也就是等于0,如果还大于0,说明还有多个数字,那就再进行同样的操作。
代码一(c++):
class Solution {
public:
int addDigits(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num = num / 10;
}
if (sum > 9) return addDigits(sum);
else return sum;
}
};
思路二:
既然题目里也鼓励我们继续思考不用循环的方式,那就一定是有规律可循。我们可以简单地列一下:
数字 | 结果 |
---|---|
0 | 0 |
1 | 1 |
2 | 2 |
3 | 3 |
4 | 4 |
5 | 5 |
6 | 6 |
7 | 7 |
8 | 8 |
9 | 9 |
10 | 1 |
11 | 2 |
12 | 3 |
13 | 4 |
14 | 5 |
15 | 6 |
16 | 7 |
17 | 8 |
18 | 9 |
19 | 1 |
20 | 2 |
21 | 3 |
就列这么多了,我们可以发现,结果除了第一个0以外,都在19之间循环。而且可以发现,其除以9的余数,为0时,对应的结果是9,而不为0时,余数等于对应的结果,那么代码就呼之欲出啦
代码二(c++):
class Solution {
public:
int addDigits(int num) {
return num % 9 == 0 ? (num == 0 ? 0 : 9) : num % 9;
}
};
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十