首页 > 代码库 > LeetCode 258. Add Digits
LeetCode 258. Add Digits
Problem:
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 = 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?
此题最初想法是相加、判断反复循环直到找到满足的解。通过参考别人的解答发现,此题是让我们求“数根”。
由此解法一为通过循环相加判断,直到找到可行解:
class Solution { public: int addDigits(int num) { int add = 0; while (num >= 10) { while(num > 0) { add += num % 10; num /= 10; } num = add; } return num; } };
但是由于时间复杂度超过题目要求,故考虑针对“数根”的解法。
通过枚举可知:
10 1+0 = 1
11 1+1 = 2
12 1+2 = 3
13 1+3 = 4
14 1+4 = 5
15 1+5 = 6
16 1+6 = 7
17 1+7 = 8
18 1+8 = 9
19 1+9 = 1
20 2+0 = 2
于是可得出规律,每9个一循环。为处理9的倍数的情况,我们写为(n - 1) % 9 + 1。由此可得:
class Solution { public: int addDigits(int num) { return (num - 1) % 9 + 1; } };
LeetCode 258. Add Digits
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。