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

Example:

Input: 38
Output: 2 
Explanation: 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?

题意:把2一个数拆开,最终变成一个1-9的数字

最先看到题先想到的是递归拆,勉强过了

Java

 1  public int addDigits(int num) {
 2         System.out.println(num);
 3         if (num <= 9)
 4             return num;
 5         int sum = 0;
 6         while (num != 0) {
 7             sum += num%10;
 8             num = num/10;
 9         }
10         return addDigits(sum);
11     }
12 }

显然题意不可能是用这个算法,末尾也有提示说O(1) 的算法复杂度,那就只能找规律了

1-9   10 11 12 13 18  19-27

1-9   1-9                       1-9

规律就比较明显了

Java

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

 

转载于:https://www.cnblogs.com/Moriarty-cx/p/9589282.html

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐