202-快乐数

标签：哈希表数学双指针

题目信息

题目内容：

javascript

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

「快乐数」定义为：

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

示例 1：
    输入：n = 19
    输出：true
    解释：
    1 ** 2 + 9 ** 2 = 82
    8 ** 2 + 2 ** 2 = 68
    6 ** 2 + 8 ** 2 = 100
    1 ** 2 + 0 ** 2 + 0 ** 2 = 1

示例 2：
    输入：n = 2
    输出：false

提示：
    1 <= n <= 231 - 1

题解

解法一

思路：

递归计算某个数所有位数上的平方根之和
如果出现结果为1的情况直接返回true
如果出现循环(平方根之和之前出现过)，那么永远不会返回1，不是快乐数，就返回false

代码实现：

javascript

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    if(n === 1) return true
    // 计算某个数所有位数上的平方根之和
    const calcSumOfSquares = num => {
        const numArr = `${num}`.split('')
        return numArr.reduce((prev, cur) => prev + cur ** 2, 0)
    }
    let num = n
    const set = new Set()
    while(num !== 1) {
        if(set.has(num)) return false
        set.add(num)
        num = calcSumOfSquares(num)
    }
    return true
};

解法二

思路：

可以将寻找1的过程看作是一个链表的结构，链表节点的值为平方根之和，链表节点的next指向下一个节点的值，而如果是快乐数的话，1就是链表末端的值
如果不是快乐数，那么链表就会是一个循环链表，可以使用弗洛伊德循环查找算法来检测是否是循环链表

TIP

弗洛伊德循环查找算法是一种用于检测链表中是否存在循环的算法。
它通过使用两个指针，一个快指针和一个慢指针，来遍历链表，
在每一步中，慢指针移动一步，而快指针移动两步，
如果存在循环，则两个指针最终会相遇。

代码实现：

javascript

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    if(n === 1) return true
    const getNextNum = (num, steps) => {
        let res = num
        while(steps > 0) {
            res = `${res}`.split('').reduce((prev, cur) => prev + cur ** 2, 0)
            steps--
        }
        return res
    }
    let lowNode = getNextNum(n, 1)
    let fastNode = getNextNum(n, 2)
    while(fastNode !== 1 && lowNode !== fastNode) {
        lowNode = getNextNum(lowNode, 1)
        fastNode = getNextNum(fastNode, 2)
    }
    return fastNode === 1
};

202-快乐数 #

题目信息 #

题解 #

解法一 #

解法二 #

202-快乐数

题目信息

题解

解法一

解法二