LeetCode笔记：各位相加
问题
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入:
38输出: 2
解释: 各位相加的过程为：
3 + 8 = 11,1 + 1 = 2。 由于2是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
解法一
思路：
首先想到可以递归计算各个位上的数字总和，一直找到小于等于 9 的数字为止。
代码：
/**
* @param {number} num
* @return {number}
*/
var addDigits = function (num) {
// 将各位数字拆开为数组
num = ("" + num).split("");
// 使用数组的reduce方法来方便的计算数字总和
const sum = num.reduce((pre, cur) => {
// +pre + +cur 等同于 (+pre) + (+cur) :
// +pre 和 +cur 会将 pre 和 cur 转化为数字，然后将它们相加
return +pre + +cur;
});
if (sum > 9) {
// 总和大于9继续递归计算总和
return addDigits(sum);
} else {
// 查找成功
return sum;
}
};
解法二
思路：
我们先枚举下 20 以内的结果
数字：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
结果：0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 ...
可以观察到除了开始的 0 之外，结果是按照 1-9 循环的。因为 9 之后就是 1，所以我们尝试对 9 取余数，发现余数就是我们想要的结果，唯一的区别是余数为 0（9 的倍数）的时候，结果应该直接取 9。
代码：
/**
* @param {number} num
* @return {number}
*/
var addDigits = function (num) {
// 特殊情况0，直接返回
if (num === 0) return 0;
// 取得9的余数
const n = num % 9;
// 如果是9的倍数，直接返回9
// 如果不是，返回余数
return n === 0 ? 9 : n;
};
解法三
思路：
还能再简化上面的方案，因为对 9 取余数得到 0 的时候，我们要用 9 作为返回值，这个情况需要特殊处理，能不能做个转换把余数 0 和其他情况兼容起来呢？我们尝试把 num 往左偏移一位（num - 1）再取 9 的余数。
数字： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
偏移(num - 1)： -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...
取余(num - 1) % 9：-1 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 ...
结果： 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 ...
可以看到(num - 1) % 9和最终结果值只差 1，而且还兼容了 num 为 0 的情况。
代码：
/**
* @param {number} num
* @return {number}
*/
var addDigits = function (num) {
// num往左偏移一位后对9取余，余数再+1，把9的倍数和不是倍数的数字统一出一个算法
return ((num - 1) % 9) + 1;
};
评论