Given a non-negative integer num
, repeatedly add all its digits until the result has only one digit.
Example:
Input: 38Output: 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 }