快乐数

题目

题目来源：力扣（LeetCode）

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

「快乐数」定义为：

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

思路分析

根据题意，我们先列举一个例子：
我们从 19 开始，那么下一个数字是 82 (因为 1^2 + 9^2 = 82)，然后下一个数字是 68 (因为 8^2 + 2^2 = 68)，然后再下一个数字是 100 (因为 6^2 + 8^2 = 100)，我们不断重复这个过程，最后我们得到了 1，因此 19 是一个快乐数，我们的函数应该返回 true。

对于正整数 19，通过反复计算平方和得到的下一个数字，其平方和构成的链表如下所示：

我们再来举一个例子：
从 116 开始，计算它的每个位置上的数字的平方和，得到的下一个数字是 38，然后再对 38 计算其每个位置上的数字的平方和，得到的下一个数字是 73，不断重复这个过程，我们最终得到了 58，然后从58开始，再继续往下计算平方和，我们又回到了 58 。由于我们回到了一个已经计算过的数字，由此可以知道这是一个循环，最后的计算结果是不可能得到 1 的，因此 116 不是快乐数，我们的函数要返回 false。

经过上面两个例子的分析，我们可以将求快乐数这道题转换成判断一个链表是否有环。如果遍历到某个节点为 1 时，说明链表有环，那么这个正整数是快乐数，如果遍历到重复的节点值，说明链表有环，那么这个正整数就不是快乐数。

判断链表是否有环，通常有两种方法，一种是使用哈希表来检测，另一种是使用快慢指针法。(详细步骤参阅：环形链表)。

代码实现

快慢指针法

const isHappy = function(n) {
    let slow = n;
  let fast = getNext(n);
  while (slow != fast && fast != 1) {
      slow = getNext(slow);
    fast = getNext(getNext(fast));
  }
  return fast === 1;
}
const getNext = function(n) {
    let temp = 0;
  while (n) {
      temp += (n % 10) * (n % 10);
    n = Math.floor(n / 10);
  }
  return temp;
}