Happy Number

202. 快乐数

分析

计算每位数字的平方和
- 创建一个函数 happy(n)，计算整数 n 每位数字的平方和
检测循环
- 使用哈希集合记录每次计算的结果，防止无限循环
- 如果平方和结果重复出现，说明进入了死循环，返回 false
- 如果平方和结果变成 1，返回 true

时间复杂度

时间复杂度 O(logn)

空间复杂度

空间复杂度为 O(logn)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    // 辅助函数：计算一个数的每位数字的平方和
    int happy(int n)
    {
        int sum = 0;
        while (n)
        {
            int t = n % 10;      // 取出最低位数字
            sum += t * t;        // 平方后累加
            n /= 10;             // 去掉最低位
        }
        return sum;
    }

    // 主函数：判断是否为快乐数
    bool isHappy(int n)
    {
        std::unordered_set<int> hash;  // 记录已出现的平方和结果

        while (n != 1)
        {
            n = happy(n);              // 计算平方和
            if (hash.count(n))         // 如果结果重复出现，说明进入循环
                return false;
            hash.insert(n);            // 记录当前结果
        }
        return true;                   // 最终变成 1，返回 true
    }
};