您现在的位置是：首页 >学无止境 >LeetCode-202.快乐数（C/C++）网站首页学无止境

题目描述

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 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：

输入：n = 2
输出：false

提示：

• 1 <= n <= 2^31 - 1

题解

思路：首先根据快乐数的定义，1.为正整数2.每一次将该数替换为它每个位置上的数字的平方和，重复这个过程直到结果最后变为 1。其次对于这个替换过程分析，这个过程持续到最后有三种结果：

1. 最终会得到 1。如示例1
2. 最终会进入循环。如116

    3.值会越来越大，最后接近无穷大。如示例2，2^2=4,4^2=16........

第三个情况比较难以检测和处理。我们怎么知道它会继续变大，而不是最终得到 1 呢？我们可以仔细想一想，每一位数的最大数字的下一位数是多少。

对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。

即使在代码中你不需要处理第三种情况，你仍然需要理解为什么它永远不会发生，这样你就可以证明为什么你不处理它。

根据以上分析我们判断一个整数是否为快乐数，我们算法核心在于解决两个问题：

1. 给一个数字 n，它的下一个数字是什么？
2. 如何按照一系列的数字来判断我们是否进入了一个循环。

根据这两个问题进行程序设计，第 1 部分我们按照题目的要求做数位分离，求平方和。

第 2 部分可以使用哈希集合完成。每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。这里使用C++实现，另外可以用第二种方法快慢指针法也称Floyd判圈算法（龟兔赛跑算法），如下介绍这两种，还有第三种官方提的数学方法，发现数学规律，硬编码哈希集合。

• 哈希集合检测法

具体步骤如下：

1. 定义一个无序集合seen，用于存储已经出现过的数。

2. 当n不等于1时，继续循环。

3. 如果n已经在集合seen中出现过，说明进入了循环，返回false。

4. 将当前的n插入到集合seen中。

5. 计算当前n的各个数字的平方和，更新n为这个和。

6. 如果n等于1，返回true，表示这个数是“快乐数”。

这个算法的核心思想是通过不断计算一个数的各个数字的平方和，直到结果为1或者进入循环。如果结果为1，那么这个数就是“快乐数”；如果进入了循环，那么这个数就不是“快乐数”。

实现代码：（C++）

class Solution { 
public: 
    bool isHappy(int n) { 
        unordered_set<int> seen; // 使用集合记录已出现过的数
        while (n != 1) { 
            if (seen.find(n) != seen.end()){ // 如果发现之前已经出现过该数字，说明进入死循环 
                return false; 
            } 
            seen.insert(n); // 将当前的n插入到集合seen中
            int num = 0;
            while (n > 0) {
                int digit = n % 10; // 获取n的最后一位数字
                num += digit * digit; // 将digit的平方加到num上
                n /= 10; // 去掉n的最后一位数字
            }
            n = num;  // 更新n为当前数的各个数字平方和
        }
        return true; // 如果n等于1，返回true，表示这个数是“快乐数”
    }
};

时间复杂度分析：

• 内层循环：每次计算数字平方和的时间复杂度为 O(d)，其中 d 是当前数字的位数。由于每次迭代后数字会显著减小（例如 n=999 变换后为 243），位数 d 会快速减少，整体可视为 O(log n)。

• 外层循环：根据数学研究，快乐数的检测过程要么收敛到 1，要么进入长度为固定值的循环（如 4 → 16 → 37 → ... → 4）。因此，循环次数 k 的上界是一个常数（约几十次），时间复杂度为 O(1)。由此可以写出硬编的第三种方法，直接写出 4 → 16 → 37 → ... → 4的集合，再检测。

综上，时间复杂度为 O(1)。

空间复杂度分析：

• 哈希集合 seen 存储中间结果。由于循环次数有固定上限（如最多存储数百个数值），空间复杂度为 O(1)。

• 龟兔赛跑算法

Floyd判圈算法（龟兔赛跑算法）

Floyd判圈算法的核心思想是使用两个指针（通常称为“慢指针”和“快指针”）来遍历数列。慢指针每次移动一步，而快指针每次移动两步。如果存在循环，快指针和慢指针最终会在某个点相遇。如果没有循环，快指针会先到达数列的终点（在这种情况下是1）。

实现步骤：

1. 初始化指针：慢指针和快指针都从起始数n开始。
2. 移动指针：慢指针每次移动一步，快指针每次移动两步（即先移动一步，然后再次移动一步）。
3. 检测循环：如果慢指针和快指针相遇，说明存在循环，返回false；如果快指针到达1，说明n是快乐数，返回true。

看官方的图解，我录成GIF形象看，链里存在环，慢的乌龟🐢会和快的兔子🐇相遇，说明存在循环，快乐不了了，返回false，也许龟兔相遇不是真正的快乐~

 实现代码：（C语言）

bool isHappy(int n) {
    // 定义一个辅助函数 getSquareSum，用于计算数字 num 的各个数字的平方和
    int getSquareSum(int num) {
        int sum = 0; // 初始化平方和为0
        while (num > 0) { // 当 num 大于0时，继续循环
            int digit = num % 10; // 获取 num 的最后一位数字
            sum += digit * digit; // 将该数字的平方加到 sum 上
            num /= 10; // 去掉 num 的最后一位数字
        }
        return sum; // 返回计算得到的平方和
    }

    int slow = n, fast = n; // 初始化两个指针 slow 和 fast，都指向 n
    do {
        slow = getSquareSum(slow);  // 移动一步，slow 更新为它各个数字的平方和（乌龟启动！！）
        fast = getSquareSum(fast);  // 移动一步，fast 更新为它各个数字的平方和（兔子启动！！）
        fast = getSquareSum(fast);  // 再移动一步，fast 以两倍速度前进，更新为它各个数字的平方和
    } while (slow != fast); // 如果 slow 和 fast 不相同，继续循环

    return slow == 1; // 如果 slow 最终等于1，返回 true，表示 n 是快乐数，否则返回 false，快乐了！
}

时间复杂度

• getSquareSum函数：这个函数的时间复杂度是O(log(n))，因为我们需要遍历num的每一位数字。

• isHappy函数：在isHappy函数中，我们最多需要遍历n次，所以isHappy函数的时间复杂度是O(nlog(n))。

所以，整个算法的时间复杂度是O(nlog(n))。

空间复杂度

• slow和fast指针：在isHappy函数中，我们只使用了两个额外的变量slow和fast，所以空间复杂度是O(1)。

所以，整个算法的空间复杂度是O(1)。

• 硬编码哈希集检测法

下一个值可能比自己大的最大数字是什么？根据我们之前的分析，我们知道它必须低于 243。因此，我们知道任何循环都必须包含小于 243 的数字，用这么小的数字，编写一个能找到所有周期的强力程序并不困难。

如果这样做，您会发现只有一个循环：4→16→37→58→89→145→42→20→4。所有其他数字都在进入这个循环的链上，或者在进入 1 的链上。

因此，我们可以硬编码一个包含这些数字的散列集，如果我们达到其中一个数字，那么我们就知道在循环中。

class Solution { // 定义一个名为Solution的类
public: // 定义公共成员函数
    bool isHappy(int n) { // 定义一个名为isHappy的成员函数，用于判断一个数是否为快乐数，参数为整数n
        // 检查当前数n是否为1或者不在cycle_members中，如果是1，则返回true；如果不在，继续循环
        while (n != 1 && cycle_members.find(n) == cycle_members.end()) {
            n = get_next(n); // 调用私有成员函数get_next，计算下一个数
        }
        return n == 1; // 如果n变为1，则返回true，表示该数是快乐数；否则返回false
    }
private: // 定义私有成员
    // 定义一个集合，用于存放可能进入循环的数，这些数不是快乐数
    std::unordered_set<int> cycle_members = {4, 16, 37, 58, 89, 145, 42, 20};

    // 定义一个私有成员函数get_next，用于计算给定数的下一个数
    int get_next(int number) {
        int total_sum = 0; // 初始化一个变量，用于存放各个位数的平方和
        // 当number大于0时，循环计算每一位上的数字的平方和
        while (number > 0) {
            int digit = number % 10; // 取number的最后一位作为digit
            total_sum += pow(digit, 2); // 计算digit的平方，并加到total_sum中
            number /= 10; // 去掉number的最后一位
        }
        return total_sum; // 返回计算得到的平方和，作为下一个数
    }
};

时间空间复杂度同法一。 

快乐时间：（你不是真正的快乐~）

从官方题解学习，做快乐人~

学习来源：

力扣官方题解
链接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/