当前位置：首页 > article >正文

leetcode 面试经典 150 题：快乐数

article 2025/1/15 6:05:28

链接	快乐数
题序号	202
题型	数组
解题方法	哈希表
难度	简单
熟练度	✅✅✅✅

题目

编写一个算法来判断一个数 n 是不是快乐数。
[快乐数] 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1²+ 0² + 0² = 1
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 2³¹ - 1

题解

核心思想：使用哈希表来记录已经出现过的数字，如果在计算过程中某个数字重复出现，说明进入了循环，返回 false；如果最终计算结果为 1，返回 true。
复杂度：时间复杂度O(logn)，因为每次计算下一个数的时间复杂度为 O(logn)；空间复杂度O(1)，不需要额外的存储空间。
c++ 实现算法：

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen; // 用于存储已经出现过的数字，检测循环
        
        //如果 find(n) 返回 seen.end()，表示 n 不存在于集合中，查找失败。
        //如果 find(n) 返回的迭代器不是 seen.end()，表示 n 存在于集合中，查找成功。
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);     // 将当前数字加入集合
            n = getNext(n);     // 计算下一步的平方和
        }
        return n == 1;          // 如果 n == 1，返回 true；否则进入循环，返回 false
    }

private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10; // 提取个位数,如果 n = 123，则 digit = 123 % 10 = 3
            sum += digit * digit; // 累加平方
            n /= 10;             // 去掉个位,如果 n = 123，执行 n /= 10 后，n = 12
        }
        return sum;
    }
};

算法推演：

初始值：输入数字：n = 2 seen 集合：空集合 {}

第一步：计算平方和
当前数字：n = 2
计算平方和： 2²=4
更新数字：n = 4 检查 4 是否在 seen 集合中：否，将 4 加入集合。
集合更新为：{2}

第二步：计算平方和
当前数字：n = 4
计算平方和： 4²=16
更新数字：n = 16 检查 16 是否在 seen 集合中：否，将 16 加入集合。
集合更新为：{2, 4}

第三步：计算平方和
当前数字：n = 16
计算平方和： 1²+6²=37
更新数字：n = 37 检查 37 是否在 seen 集合中：否，将 37 加入集合。
集合更新为：{2, 4, 16}

第四步：计算平方和
当前数字：n = 37
计算平方和： 3²+7²=58
更新数字：n = 58 检查 58 是否在 seen 集合中：否，将 58 加入集合。
集合更新为：{2, 4, 16, 37}

第五步：计算平方和
当前数字：n = 58
计算平方和： 5²+8²=89
更新数字：n = 89 检查 89 是否在 seen 集合中：否，将 89 加入集合。
集合更新为：{2, 4, 16, 37, 58}

第六步：计算平方和
当前数字：n = 89
计算平方和： 8²+9²=145
更新数字：n = 145 检查 145 是否在 seen 集合中：否，将 145 加入集合。
集合更新为：{2, 4, 16, 37, 58, 89}

第七步：计算平方和
当前数字：n = 145
计算平方和： 1²+4²+5²=42
更新数字：n = 42 检查 42 是否在 seen 集合中：否，将 42 加入集合。
集合更新为：{2, 4, 16, 37, 58, 89, 145}

第八步：计算平方和
当前数字：n = 42
计算平方和： 4²+2²=20
更新数字：n = 20 检查 20 是否在 seen 集合中：否，将 20 加入集合。
集合更新为：{2, 4, 16, 37, 58, 89, 145, 42}

第九步：计算平方和
当前数字：n = 20
计算平方和： 2²+0²=4
更新数字：n = 4 检查 4 是否在 seen 集合中：是，说明进入循环。

结论
输入 2 会进入循环，无法到达 1，因此 2 不是一个快乐数。

循环检测
通过集合 seen，我们检测到了循环路径： 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (循环) 这是算法检测非快乐数的重要机制，避免了死循环。

c++ 完整demo：

#include <iostream>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen; // 用于存储已经出现过的数字，检测循环
        
        //如果 find(n) 返回 seen.end()，表示 n 不存在于集合中，查找失败。
        //如果 find(n) 返回的迭代器不是 seen.end()，表示 n 存在于集合中，查找成功。
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);     // 将当前数字加入集合
            n = getNext(n);     // 计算下一步的平方和
        }
        return n == 1;          // 如果 n == 1，返回 true；否则进入循环，返回 false
    }

private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10; // 提取个位数,如果 n = 123，则 digit = 123 % 10 = 3
            sum += digit * digit; // 累加平方
            n /= 10;             // 去掉个位,如果 n = 123，执行 n /= 10 后，n = 12
        }
        return sum;
    }
};

int main() {
    Solution solution;
    int n = 2;
    if (solution.isHappy(n)) {
        cout << n << " is a happy number!" << endl;
    } else {
        cout << n << " is not a happy number!" << endl;
    }
    return 0;
}