202. 快乐数 Easy

编写一个算法来判断一个数 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

解题思路

输入：一个数字 n

输出：验证 n 是否是快乐数

本题属于 哈希表 || 快慢指针 问题。

我们可以用哈希表也可以用快慢指针来解决这道题。

我们先创建一个函数 next 对当前的数持续做“各位平方和”的变换，返回下一个需要变换的值

哈希表

• 我们可以用哈希表记录每次变换后的值
• 若出现过某个中间值，说明进入循环，不是快乐数；
• 若变换后出现 1，则是快乐数

快慢指针

• 慢指针每次走一步（做一次变换），快指针每次走两步；
• 若相遇于 1 -> 快乐数；若相遇于其他数 -> 存在环，不是快乐数。
• 优点：O(1) 额外空间。

代码实现

哈希方案

python

class Solution:
    def isHappy(self, n: int) -> bool:
        # 用一个集合来存储已经出现过的数字，防止陷入无限循环
        seen = set()

        # 定义一个函数，用来计算一个数字的“各位数字平方和”
        def next(num):
            s = 0
            while num > 0:
                d = num % 10        # 取出当前数字的最后一位
                s += d ** 2         # 累加该位数字的平方
                num = num // 10     # 去掉最后一位
            return s

        # 当 n 不是 1 且没有重复出现过时，不断进行转换
        while n != 1 and n not in seen:
            seen.add(n)      # 记录当前数字，防止死循环
            n = next(n)      # 得到下一轮的数字
        
        # 如果最终 n 等于 1，则是快乐数，否则不是
        return n == 1

javascript

var isHappy = function(n) {
    const seen = new Set();

    function next(num) {
        let sum = 0;

        while (num > 0) {
            let d = num % 10;
            sum += d ** 2;
            num = Math.floor(num / 10);
        }

        return sum;
    }

    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = next(n);
    }

    return n === 1;
};

快慢指针方案

python

class Solution:
    def isHappy(self, n: int) -> bool:
        # 定义一个函数，用来计算数字的“各位数字平方和”
        def next(num):
            s = 0
            while num > 0:
                d = num % 10        # 取出当前数字的最后一位
                s += d ** 2         # 累加该位数字的平方
                num = num // 10     # 去掉最后一位
            return s
        
        # 快慢指针初始化
        # slow 每次走一步（计算一次平方和）
        # fast 每次走两步（计算两次平方和）
        slow, fast = n, next(n)

        # 循环直到：
        # 1. fast 指针走到 1（说明是快乐数）
        # 2. slow 和 fast 相遇（说明进入循环，不是快乐数）
        while fast != 1 and slow != fast:
            slow = next(slow)           # 慢指针走一步
            fast = next(next(fast))     # 快指针走两步
        
        # 如果 fast 最终到达 1，则为快乐数
        return fast == 1

javascript

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    function next(num) {
        let s = 0;

        while (num > 0) {
            const d = num % 10;
            s += d ** 2;
            num = Math.floor(num / 10);
        }

        return s;
    }

    let slow = n;
    let fast = next(n);
    while (fast !== 1 && slow !== fast) {
        slow = next(slow);
        fast = next(next(fast));
    }

    return fast === 1;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

202 国际版

202 中文版