Shouyu

Appearance

代码随想录 哈希表 202 快乐数 ​

题目链接：https://leetcode.cn/problems/happy-number/description/

文章讲解：https://programmercarl.com/0202.快乐数.html

题目描述 ​

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

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

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

示例：

输入：19 输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

思路 ​

观察到

  • 如果数字最终变为 1，则是快乐数。

  • 如果数字进入一个无限循环（即重复出现某个数字），则不是快乐数。

因此，我们需要检测是否进入了循环。只有这两种结果吗？其实是个数学问题，已经证明对于任何正整数 n，其平方和的计算过程只有这两种可能。

因为：

  • 平方和的计算过程是一个有限状态机，数字的范围是有限的（对于 n 位数，平方和最多是 81 * n）。

  • 根据鸽巢原理，如果无限计算下去，一定会重复出现某个数字，从而进入循环。

如何检测循环？

可以使用一个哈希集合（unordered_set）来记录已经出现过的数字。如果在计算过程中，某个数字重复出现，说明进入了循环，直接返回 false

算法步骤

  1. 初始化一个哈希集合 result 来记录已经出现过的数字。

  2. 进入一个循环：

    • 计算当前数字 n 的各位数字平方和 sum。

    • 如果 sum == 1，返回 true。

    • 如果 sum 已经在 result 中，说明进入循环，返回 false。

    • 否则，将 sum 加入 result，并将 n 更新为 sum

  3. 重复上述步骤。

  • 时间复杂度：O(log n) 或 O(m)，其中 m 是数字的位数。每次计算平方和的时间是 O(log n)，---》》》数字 n 的位数是 ⌊log10n⌋+1（即 O(log⁡n)）。而循环的次数取决于数字是否进入循环。

  • 空间复杂度：O(m)，哈希集合存储已经出现过的数字，最坏情况下会存储所有中间结果。

扩展 ​

方法：快慢指针法 ​

类似于检测链表是否有环，可以用两个指针：

  • 慢指针：每次计算一次平方和。

  • 快指针：每次计算两次平方和。

如果快指针和慢指针相遇：

  • 相遇点为 1 → 是快乐数。

  • 相遇点不为 1 → 不是快乐数。

cpp
int getSum(int n) {
    int sum = 0;
    while (n) {
        sum += (n % 10) * (n % 10);
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow = n;
    int fast = getSum(n); // 快指针先走一步
    while (fast != 1 && slow != fast) {
        slow = getSum(slow); // 慢指针走一步
        fast = getSum(getSum(fast)); // 快指针走两步
    }
    return fast == 1;
}

复杂度分析 ​

  • 时间复杂度：O(log n)，和之前相同。

  • 空间复杂度：O(1)，不再需要哈希集合。

当然还有数学法，所有不快乐的数最终都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环解决，我们程序员不用数学方法，这里不是重点。