Skip to main content

快乐数

· 5 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——202题​

💡 参考代码：​

/**
 * 计算一个数各个位上数字的平方和
 * @param n 输入的正整数
 * @return 各个位数字平方和的结果
 */
int getSum(int n) {
    int sum = 0;
    // 逐位提取数字并计算平方和
    while (n > 0) {
        int digit = n % 10;     // 获取个位数字
        sum += digit * digit;   // 累加该数字的平方
        n /= 10;                // 去掉已处理的个位数字
    }
    return sum;
}

/**
 * 判断一个数是否为快乐数
 * 快乐数定义：不断将数替换为各位数字的平方和，最终结果为1的数
 * 非快乐数会进入无限循环，需要检测循环避免无限执行
 * 
 * @param n 待判断的正整数
 * @return 如果是快乐数返回true，否则返回false
 */
bool isHappy(int n) {
    // 使用快慢指针法检测循环
    // slow指针每次计算一次平方和
    // fast指针每次计算两次平方和
    // 如果存在循环，快慢指针终将相遇
    // 如果n是快乐数，fast指针会先到达1
    int slow = n;
    int fast = n;
    
    do {
        // 慢指针移动一步
        slow = getSum(slow);
        // 快指针移动两步
        fast = getSum(getSum(fast));
        
        // 如果快指针到达1，说明是快乐数
        if (fast == 1) {
            return true;
        }
    } while (slow != fast);  // 当快慢指针相遇时，说明出现了循环
    
    // 快慢指针相遇且不为1，说明进入了循环，不是快乐数
    return false;
}

📖 总结：​

点击展开题目总结

🤔 快乐数

1️⃣ 题目核心信息​

🎯 功能描述：判断一个正整数是否为快乐数。快乐数的定义是：将该数替换为它每个位置上的数字的平方和，重复这个过程直到这个数变为 1（为快乐数），或者进入无限循环但始终变不到 1（非快乐数）。

📥 输入输出：

  • 输入：n - 待判断的正整数（1 <= n <= 2^31 - 1）
  • 输出：布尔值，如果是快乐数返回 true，否则返回 false

2️⃣ 实现原理​

💡 核心思路：使用快慢指针法（Floyd 判圈算法）检测是否出现循环。慢指针每次计算一次平方和，快指针每次计算两次平方和。如果存在循环，快慢指针终将相遇；如果是快乐数，快指针会先到达 1。

📋 实现步骤：

  1. 编写辅助函数 getSum 计算一个数各位数字的平方和
  2. 初始化快慢指针都指向输入数字 n
  3. 循环中慢指针移动一步，快指针移动两步
  4. 如果快指针到达 1，返回 true（是快乐数）
  5. 如果快慢指针相遇且不为 1，说明进入循环，返回 false

3️⃣ 关键点解析​

最优解使用快慢指针法，空间复杂度为 O(1)，这是经典的 Floyd 判圈算法应用。

🎯 代码技巧​

  • 使用快慢指针检测循环，避免使用额外存储空间
  • 分离计算平方和的逻辑到独立函数，提高代码可读性
  • 利用 do-while 循环结构确保至少执行一次循环体

4️⃣ 使用场景​

✅ 适用情况：​

  • 检测链表或序列中的循环
  • 数字变换类问题中判断是否进入循环状态
  • 需要常数空间复杂度的循环检测问题

⚠️ 前提条件：​

  • 输入为正整数
  • 变换过程确定且可预测

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(log n) - 每次计算平方和需要 O(log n) 时间，循环次数是常数级别
  • 💾 空间复杂度：O(1) - 只使用了常数级别的额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 输入为 1（本身就是快乐数）
  • 输入为单个数字但非 1 的情况
  • 大整数输入的情况

💥 易错点：​

  • 忘记处理快指针到达 1 的情况直接返回 false
  • 循环条件判断错误，可能导致无限循环
  • 没有正确实现各位数字平方和的计算逻辑

7️⃣ 补充说明​

以 n = 19 为例​

我们通过具体例子 n = 19 来逐步演示 isHappy 函数的执行过程：

🔢 第一步：初始化​

  • slow = 19
  • fast = 19

🔄 第二步：进入循环​

第1次循环：

  • slow = getSum(19) = 1² + 9² = 1 + 81 = 82
  • fast = getSum(getSum(19)) = getSum(82) = 8² + 2² = 64 + 4 = 68
  • 检查 fast == 1？否，68 ≠ 1
  • 检查 slow != fast？是，82 ≠ 68，继续循环

第2次循环：

  • slow = getSum(82) = 8² + 2² = 64 + 4 = 68
  • fast = getSum(getSum(68)) = getSum(100) = 1² + 0² + 0² = 1
  • 检查 fast == 1？是，返回 true

✅ 最终结果​

由于快指针 fast 在第2次循环中变为 1，函数返回 true，表明 19 是一个快乐数。

📈 getSum 函数执行过程示例​

当计算 getSum(19) 时：

  1. digit = 19 % 10 = 9，sum = 0 + 9² = 81，n = 19 / 10 = 1
  2. digit = 1 % 10 = 1，sum = 81 + 1² = 82，n = 1 / 10 = 0
  3. 返回 sum = 82

这个逐步执行过程展示了如何通过快慢指针法判断快乐数，避免了无限循环的可能。

加载评论中...