算法之快乐数 - 翁先森的博客

202.快乐数

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

「快乐数」定义为：

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

思路:

1.哈希表

每次都去拆分数字计算平方和，如果和为1，就是快乐数，如果不唯一就存在Map里头。

后面计算发现，如果说不是快乐数得话，计算的值可能会回到之前计算的某个值，也就是Map里头，所以如果说计算的结果，map里头存在，那么说明不是快乐树

1
/**
2
 * @param {number} n
3
 * @return {boolean}
4
 */
5

6
function sum(n) {
7
    n = n + ''
8
    let sum = 0
9
    for (let num of n) {
10
        sum += num * num
11
    }
12
    return sum
13
}
14
var isHappy = function (n) {
15
    let res = sum(n)
16
    let obj = {}
17
    while (res != 1) {
18
        if (res in obj) return false
19
        obj[res] = 1
20
        res = sum(res)
21
    }
22
    return true
23
}

2.快慢指针

根据题意，我们可以分析如下：

找到快乐数没有快乐数，形成环路，造成死循环。其实分析是很容易的，接下来我们看看，如何解题。

首先，我们肯定可以使用哈希表记录过程值，若找到 11，皆大欢喜。

如果在找的过程中，哈希表中已存在当前数，则证明进入了环路，也就是死循环了！

此时，我们就可以判断当前数不是一个快乐数了~

但是，为了降低空间复杂度，我们选择使用快慢指针来解决，流程如下：

创建一个慢指针，一次走一步，再创建一个快指针，一次走两步。当快慢指针相遇，代表形参环路，该数不是快乐数。若指针移动过程中，找到了 11，则当前数是一个快乐数。

1
let getNext = function (n) {
2
    return n.toString().split('').map(i => i ** 2).reduce((a, b) => a + b);
3
}
4
let isHappy = function (n) {
5
    let slow = n;
6
    let fast = getNext(n);
7
    while(fast !== 1 && fast !== slow){
8
        slow = getNext(slow);
9
        fast = getNext(getNext(fast));
10
    }
11
    return fast === 1;
12
};