题解 | #快乐数#

快乐数

https://www.nowcoder.com/practice/293b9ddd48444fa493dd17da0feb192d

题目链接

快乐数

题目描述

给定一个正整数，请你判断这个数是不是快乐数。

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

示例 1: 输入: 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: 输入: 111 输出: false

解题思路

这道题的核心是判断一个数字经过一系列"各位数字平方和"的变换后，是最终能到达 1，还是会陷入一个无限循环。

1. 变换序列与循环 这个变换过程 n -> next_n 会生成一个数字序列。

如果一个数是快乐数，这个序列的终点是 1。
如果不是快乐数，序列永远不会到达 1。由于变换后的数值大小有上限（例如，对于任意一个4位数，其各位数字平方和最大为 9^2 * 4 = 324），所以序列中的数字不会无限增大，最终必然会重复某个已经出现过的数字，从而形成一个环 (Cycle)。

2. 环检测 因此，这个问题就转化为了一个经典的环检测问题。我们只需要判断这个序列是最终汇入 1，还是陷入了其他循环。

最直观的环检测方法是使用哈希集合 (Hash Set)。

创建一个哈希集合 seen，用来存储所有在变换过程中出现过的数字。
从给定的数字 n 开始，进入一个循环，反复计算下一个数。
在循环的每一步：
- 首先判断当前数字 n 是否等于 1。如果是，则找到了快乐的结局，返回 true。
- 然后判断当前数字 n 是否已经在 seen 集合中。如果是，则说明我们进入了一个循环，永远无法到达 1，返回 false。
- 如果以上都不是，说明这是一个新数字，将它加入 seen 集合，然后计算出下一个数，继续循环。

为了代码清晰，我们可以将"计算各位数字平方和"的逻辑提取为一个辅助函数。

代码

cpp
java
python

class Solution {
private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return bool布尔型
     */
    bool happynum(int n) {
        set<int> seen;
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }
};

import java.util.*;

public class Solution {
    private int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return bool布尔型
     */
    public boolean happynum(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return bool布尔型
#
class Solution:
    def get_next(self, n: int) -> int:
        total_sum = 0
        while n > 0:
            n, digit = divmod(n, 10)
            total_sum += digit ** 2
        return total_sum

    def happynum(self, n: int) -> bool:
        # write code here
        seen = {n}
        while n != 1:
            n = self.get_next(n)
            if n in seen:
                return False
            seen.add(n)
        return True

算法及复杂度

算法: 哈希集合/有序集合（用于环检测）
时间复杂度:
- C++: $\mathcal{O}(\log n \cdot \log(\log n))$ 。变换序列的长度约为 $\mathcal{O}(\log n)$ 。对于 std::set，每次插入和查找操作需要 $\mathcal{O}(\log K)$ 时间，其中 K 是集合中的元素数量（最多也为 $\mathcal{O}(\log n)$ ）。
- Java/Python: $\mathcal{O}(\log n)$ 。对于哈希表，每次操作平均时间为 $\mathcal{O}(1)$ ，总时间由变换序列的长度主导。
空间复杂度: $\mathcal{O}(\log n)$ 。空间由集合 seen 使用。其存储的元素数量与时间复杂度的分析类似，也由 n 的位数相关。