Add Digits
Add Digits
叶枫啦啦 发表于4个月前
Add Digits
  • 发表于 4个月前
  • 阅读 5
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

题目:

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 = 111 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

解决:

① 将每位数相加,知道它们的和为个位数为止。耗时3ms。

public class Solution {
    public int addDigits(int num) {
        while(num > 9){
            int sum = 0;
            while(num > 0){
                sum += (num % 10);
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
}

②我们先来观察1到20的所有的树根:

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

根据上面的列举,我们可以得出规律,每9个一循环,所有大于9的数的树根都是对9取余,那么对于等于9的数对9取余就是0了,为了得到其本身,而且同样也要对大于9的数适用,我们就用(n-1)%9+1这个表达式来包括所有的情况,所以解法如下,耗时2ms:

public class Solution {
    public int addDigits(int num) {
        if (num <= 9) {
            return num;
        }
        return (num -1) % 9 + 1;
    }
}

③ 同一个思路

public class Solution {
    public int addDigits(int num) {
        return num % 9 == 0 ? (num == 0 ? 0 : 9) : num % 9;
    }
}

共有 人打赏支持
粉丝 0
博文 213
码字总数 96569
×
叶枫啦啦
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: