leetcode解题报告258. Add Digits

题目地址

难度是easy

题目描述

给定一个正整数，将其每一位上的数相加起来，得到另一个数，如果该数不是个位数，重复以上操作，直到得到一个个位数。 提示，这可以有 O(1) 复杂度的算法

我的思路

模拟操作类的题目，直接暴力实现题目操作即可。 题目提示有 O(1) 复杂度的算法，应该是有公式，直接算出来。但没想到这公式。

我的代码

class Solution { public: int addDigits(int num) { while (num / 10) { int a = 0; while (num) { a += num % 10; num /= 10; } num = a; } return num; } };

阅读官方题解

没有官方题解，但网上有很多资源

暴力算法和我的差不多。至于那个 O(1) 算法果然是有公式。在数学上，题目所求的就是数字根(digital root), 公式是(a-1)%9+1

思想核心总结

学会数字根公式 有时候，一些公式不懂时，可以尝试看几个例子，找规律，也许能找到公式。比如这个数字根公式。