LeetCode258-Add Digits

题目

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

分析

解法一:暴力辗转相除

照着题意顺着下来,我们很容易利用辗转相除,连续与10取模得到各个位的数字,再累加起来,然后判断累加和是否是个位数,若是停止,若不是,则还要让这个累加和参与下一次的辗转相除,进而得到新的累加和,如此往复。

解法二:取模运算

解法一思路很明确,但利用双重循环实现效率着实不高。究其原因是没有对题目进行深入的挖掘,我们不妨观察下1 – 20的结果,看是否有规律:

0 –   0

1  –   1          10  –  1          19  –  1

2  –  2          11  –  2          20  – 2

3  –  3          12  –  3

4  –  4          13  –  4

5  –  5          14  –  5

6  –  6          15  –  6

7  –  7           16  –  7

8  –  8          17  –  8

9  –  9          18   –  9

不难看出,每9个数便产生一次循环,即结果与取9模正相关,但不是直接取9的模,因为我们发现有个特殊情况:当num为9的倍数时,此时结果应是9,而不是num % 9 = 0,所以我们需要用下面这个式子才能一概而论:(num – 1) % 9 + 1。

代码

解法一

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

解法二

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

Leave a Comment.