小样儿,是不是以为题目哩我写错别字了?
1. 题目
给出一个非负整数 num,反复的将所有位上的数字相加,直到得到一个一位的整数
1.1 举个栗子
输入:num=38输出:2解释:过程如下:3 + 8 = 11, 1 + 1 = 2. 因为 2 只有一个数字,返回 2
输入:num=9输出:9解释:9<10,返回 9.
1.2 挑战
你可以不用任何的循环或者递归算法,在 O(1) 的时间内解决这个问题么?
2. 解法1
思路就是题目的要求
两层循环
外层循环判断num的结果是不是小于10了
内层循环对当前数字的各个位进行相加
public class Solution { /** * @param num: a non-negative integer * @return: one digit */ public int addDigits(int num) { while(num >=10){ int result = 0; while(num!=0){ result += num%10; num=num/10; } num = result; } return num; }}
3. 解法2
题目既然敢问能否在 O(1) 的时间内解决这个问题
那就说明肯定可以
不用循环,那必然是有规律的
那我们就来找找规律
拿出我的纸笔
果然,规律就是
从1开始,结果依次是1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9····
那就是在给定值>=1的时候,进行取余,余数就是结果
规律找到了,代码就简单了,一行就能搞定
public class Solution { /** * @param num: a non-negative integer * @return: one digit */ public int addDigits(int num) { return num==0?num: (num%9==0?9:num%9); }}
4. 解法3
public class Solution { /** * @param num: a non-negative integer * @return: one digit */ public int addDigits(int num) { while(num>=10){ num = num/10+num%10; } return num; }}
这个解法嘛
我也不知道为什么
反正对了
具体为什么对,还需要大神来证明一下了
文/戴先生@2020年6月28日
---end---
更多精彩推荐