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
. Since2
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 }
所有评论(0)