【LeetCode】202. 快乐数（简单）——代码随想录算法训练营Day06

题目链接：202. 快乐数

题目描述

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

「快乐数」?定义为：

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

如果?n?是?快乐数?就返回?true?；不是，则返回?false?。

示例 1：

输入：n = 19

输出：true

解释：

12?+ 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

示例 2：

输入：n = 2

输出：false

提示：

• 1 <= n <= 231 - 1

文章讲解：代码随想录

题解1：

思路：这里将题目描述中的一次替换操作称为1次 happy 操作。如果一个数是快乐数，则在有限次 happy 操作后它会变为1；如果不是快乐数，则进行无限次 happy 操作也不会变为1。

有一个重要结论：非快乐数在无限次 happy 操作中，会出现曾经出现过的 happy 操作的结果，即在求和的过程中，sum 会重复出现。

证明可以先证这个问题是个有限状态，因为任何正整数 n 的每个位上的数字的平方和都小于或等于（9^2 × 位数），因此对于任何给定的 n，其平方和有一个上限。随着平方和的重复计算，新得到的数要么减小，要么在有限范围内波动，如下图。

再证收敛性：如果在某个点达到1，之后就永远是1，如果没有达到1，由于是有限状态，根据狄利克雷原则，无限次迭代必导致状态重复；所以算法最终会收敛到一个有限序列。

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    const hashSet = new Set();

    // 返回对 n 进行一次 happy 操作的结果
    const happy = function (n) {
        let res = 0;
        while (n > 0) {
            const d = n % 10;
            res += d * d;
            n = Math.floor(n / 10);
        }
        return res;
    };

    // 持续对 n 进行 happy 操作，如果出现1，则为快乐数，若出现了曾出现过的数，则不是快乐数。
    while (!hashSet.has(n)) {
        if (n === 1) {
            return true;
        }
        hashSet.add(n);
        n = happy(n);
    }
    return false;
};

分析：时间复杂度为 O(logn)，空间复杂度为 O(logn)。

收获

(1) 继续体验哈希表的使用场景，判断一个数在不在集合中，就可以使用哈希表。

(2) 与数字有关的场景，数字范围大哈希表的数据结构使用 Set，数字范围小哈希表的数据结构使用 Array。