LeetCode笔记：快乐数

#leetcode

问题

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入： 19

输出： true

解释：

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

示例 2：

输入： n = 2

输出： false

提示：

  • 1 <= n <= 231 - 1

解法

思路：

有两种情况

  1. 循环求平方和得到结果 1，为 true
  2. 死循环，得不到结果 1，这时候用快慢指针判断是否有两个指针相遇的情况，来判定是否陷入死循环

代码：

/**

 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
  let after = n; // 当前值
  let forward = nextNum(n); // 向前走一步

  // 以下两种情况退出循环
  // forward == after: 快慢指针相遇
  // forward == 1: 取到了结果1
  while (forward != after && forward != 1) {
    after = nextNum(after); // 慢指针向前走一步
    forward = nextNum(nextNum(forward)); // 快指针向前走两步
  }

  // 返回结果
  return forward == 1;

  // 取得下一个数字，即当前每个位置数字的平方和
  function nextNum(n) {
    return (n + "")
      .split("")
      .map((a) => a ** 2)
      .reduce((x, y) => x + y);
  }
};

参考

评论