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;
};

参考

评论