JavaScript：202. 快乐数（快慢指针）

题目说明

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

 

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解题思路一

1. 假如该数为快乐数
   1. 先求出n的位平方和，并替换n的值。
   2. 判断其平方和(n)是否 === 1，等于1 返回true，不等，继续求n的位平方和
2. 假如该数不为快乐数
   1. 将步骤1中求出的所有n，存在数组中。
   2. 存入数组中时，判断其是否已经在数组中，若在，说明数字进入了循环，返回false

代码实现一

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    if (n === 1) {
        return true
    }
    let res = 0, front = [n];
    while(res != 1) {
        res = 0;
        while(n) {
            let ys = n % 10;
            n = Math.floor(n / 10);
            res += ys * ys;
        }
        n = res;
        front.push(n);
        if ((new Set(front)).size < front.length) {
            return false
        }
    }
    return true
};

上面，我通过set的特性来判断是否存在重复数字，我们也可以用Array.includes()来判断。

解题思路二

1. 根据思路一，我们可以进行优化，并可以通过快慢指针判断是否存再循环。
2. 在循环中，慢指针一次走一步，快指针一次走两步，最后快指针必定会和慢指针相遇。若相遇说明存在循环，返回false，若不存在返回true。

代码实现二

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    if (n === 1) {
        return true
    }
    let slow = n = getSum(n)
    let fast = n = getSum(n)
    while(n != 1 && slow !== fast) {
        slow = getSum(n)
        fast = getSum(getSum(fast))
        n = slow
    }
    return n === 1
};
var getSum = function(n) {
    return n = (n+'').split('').reduce(function(sum, item){
        return sum + item * item;
    },0)
}