首页 > 代码库 > Leetcode:258.Add Digits

Leetcode:258.Add Digits

题目:

  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?

  给定非负整数,将每一位进行相加,重复进行,直到最后为一位。

求解思路:

  (1) 不考虑时间复杂度要求,使用循环迭代,直到得到一位数为止。 

1 public class Solution {
2     public int addDigits(int num) {
3         while(num/10!=0)
4         {
5             num = num/10 +(num%10);
6         }
7         return num;
8     }
9 }

  (2) 为了达到时间复杂度为O(1)的要求,通过观察[10,40]中整数对应的结果,得出公式。

1 public class Solution {
2     public static void main(String args[]){
3         for(int i = 10;i <= 40; i++){
4             System.out.print(i + "-" + addDigits(i) + "\t");
5         }
6     }
7 }

根据上述代码结果:

10-1  11-2  12-3  13-4  14-5  15-6  16-7  17-8  18-9

19-1    20-2    21-3  22-4  23-5  24-6  25-7  26-8  27-9

28-1  29-2  30-3  31-4  32-5  33-6  34-7  35-8  36-9 

37-1  38-2  39-3  40-4

得到公式:结果=(num-1)%9+1

所以根据上述公式,时间复杂度为O(1)的代码如下:

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

 

Leetcode:258.Add Digits