景真

外观

快乐数

约 3337 字大约 11 分钟

双指针数学哈希表

2025-02-26

202. 快乐数

编写一个算法来判断一个数 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

我们可以先举几个例子。我们从 7 开始。则下一个数字是 49（因为 72=497^2=49），然后下一个数字是 97（因为 42+92=974^2+9^2=97）。 我们可以不断重复该的过程，直到我们得到 1。因为我们得到了 1，我们知道 7 是一个快乐数，函数应该返回 true。

再举一个例子，让我们从 116 开始。通过反复通过平方和计算下一个数字，我们最终得到 58，再继续计算之后，我们又回到 58。 由于我们回到了一个已经计算过的数字，可以知道有一个循环，因此不可能达到 1。所以对于 116，函数应该返回 false。

根据我们的探索，我们猜测会有以下三种可能。

  1. 最终会得到 1。
  2. 最终会进入循环。
  3. 值会越来越大，最后接近无穷大。

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

DigitsLargestNext
1981
299162
3999243
49999324
1399999999999991053

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

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

哈希集合

哈希集记录已经出现过的数字，避免死循环。不断计算下一个数字的平方和，直到 n 等于 1 或者已出现过。计算平方和时利用模10取余操作得到最低位数字，利用除以10操作去掉最低位数字。

class Solution {
    // 辅助方法：计算一个数字的各个位上的数字的平方和
    private int getNext(int n) {
        int totalSum = 0;
        // 对 n 进行逐位处理
        while (n > 0) {
            int d = n % 10; // 取出最低位数字
            n = n / 10;     // 去掉最低位数字
            totalSum += d * d; // 计算该位数字的平方并累加到总和
        }
        return totalSum; // 返回数字平方和
    }

    public boolean isHappy(int n) {
        // 用于记录已经出现过的数字，避免死循环
        Set<Integer> seen = new HashSet<>();
        // 不断计算下一个数字的平方和，直到 n 等于 1 或者出现循环
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);  // 将当前数字加入到 seen 集合中
            n = getNext(n); // 计算当前数字的平方和，作为下一个数字
        }
        // 如果 n 等于 1，则返回 true，否则返回 false
        return n == 1;
    }
}

确定这个问题的时间复杂度对于一个「简单」级别的问题来说是一个挑战。如果您对这些问题还不熟悉，可以尝试只计算 getNext(n) 函数的时间复杂度。

  • 时间复杂度： O(243⋅3+log⁡n+log⁡log⁡n+log⁡log⁡log⁡n)…=O(log⁡n)O(243 \cdot 3+\log n+\log \log n+\log \log \log n) \ldots=O(\log n) 。 查找给定数字的下一个值的成本为 O(log⁡n)O(\log n) ，因为我们正在处理数字中的每位数字，而数字中的位数由 log⁡n\log n 给定。

要计算出总的时间复杂度，我们需要仔细考虑循环中有多少个数字，它们有多大。 我们在上面确定，一旦一个数字低于 243 ，它就不可能回到 243 以上。因此，我们就可以用 243 以下最长循环的长度来代替 243 ， 不过，因为常数无论如何都无关紧要，所以我们不会担心它。 对于高于 243 的 nn ，我们需要考虑循环中每个数高于 243 的成本。通过数学运算，我们可以证明在最坏的情况下， 这些成本将是 O(log⁡n)+O(log⁡log⁡n)+O(log⁡log⁡log⁡n)…O(\log n)+O(\log \log n)+O(\log \log \log n) \ldots 。 幸运的是， O(log⁡n)O(\log n) 是占主导地位的部分，而其他部分相比之下都很小 (总的来说，它们的总和小于 log⁡n)\log n) ，所以我们可以忽略它们。

  • 空间复杂度： O(log⁡n)O(\log n) 。与时间复杂度密切相关的是衡量我们放入哈希集合中的数字以及它们有多大的指标。对于足够大的 nn ，大部分空间将由 nn 本身占用。我们可以很容易地优化到 O(243⋅3)=O(1)O(243 \cdot 3)=O(1) ，方法是只保存集合中小于 243 的数字，因为对于较高的数字，无论如何都不可能返回到它们。

快慢指针

初始化慢指针为n，初始化快指针为对n操作一次后的数，当快指针不为1且慢指针不等于快指针时，继续循环，慢指针每次走一步， 即在慢指针的基础上执行一次计算操作，快指针每次走两步，如果快指针等于1，则为快乐数；否则不是

我们不是只跟踪链表中的一个值，而是跟踪两个值，称为快跑者和慢跑者。在算法的每一步中，慢速在链表中前进 1 个节点，快跑者前进 2 个节点（对 getNext(n) 函数的嵌套调用）。

如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。

如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

class Solution {

    // 计算一个数字的各个位上的数字的平方和。该方法的时间复杂度为O(log n)
    public int getNext(int n) {
        int totalSum = 0;
        // 对 n 进行逐位处理
        while (n > 0) {
            int d = n % 10; // 取出最低位数字
            n = n / 10;     // 去掉最低位数字
            totalSum += d * d; // 计算该位数字的平方并累加到总和
        }
        return totalSum; // 返回数字平方和
    }

    // 判断一个数字是否是快乐数。
    public boolean isHappy(int n) {
        int slowRunner = n; // 初始化慢指针，指向当前数
        // 初始化快指针，指向下一个数。计算一次 getNext。重点。不然进不去下面的循环。其实是否是从同一起点出发无所谓，因为fast遇到1后以后都是1，
        // 不会因为跳过1而错认为fast不是快乐数的（而且遇到1后slow也会变成1，下一轮就会退出）。
        // 如果不是1而是循环，也不会错过条件的，因为fast和slow总会相遇。
        int fastRunner = getNext(n);
        
        // 当快指针不为1且慢指针不等于快指针时，继续循环。
        // 如果没有循环，则如上面的分析，快指针只会用log n就能到1；如果有循环，则快指针需要再走一圈才能追上慢指针。
        // 这一圈中每个数字之间的转换也遵循无循环时的规律，即以log n级别下降。所以while的时间复杂度为O(log^2 n)。
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner); // 慢指针每次走一步
            fastRunner = getNext(getNext(fastRunner)); // 快指针每次走两步
        }
        
        // 如果快指针等于1，则为快乐数；否则不是
        return fastRunner == 1;
    }
    
    // 或者
    public boolean isHappy(int n) {
        int slowRunner = n; // 初始化慢指针，指向当前数
        int fastRunner = n; // 初始化快指针，指向下一个数。计算一次 getNext
        
        // 当快指针不为1且慢指针不等于快指针时，继续循环
        while (fastRunner != 1) {
            slowRunner = getNext(slowRunner); // 慢指针每次走一步
            fastRunner = getNext(getNext(fastRunner)); // 快指针每次走两步
            if (slowRunner == fastRunner) return false;
        }
        
        // 如果快指针等于1，则为快乐数；否则不是
        return fastRunner == 1;
    }
}
初始状态：
slow = 19, fast = 19

第一轮：
slow = 82, fast = 82 -> fast = 68

第二轮：
slow = 68, fast = 68 -> fast = 100 -> fast = 1

第三轮：
slow = 100, fast = 1 -> fast = 1

第四轮：
slow = 1, fast = 1 -> fast = 1

循环结束，因为 slow 和 fast 相遇，且 slow == 1

getNext 方法

  • 时间复杂度：
    getNext 方法中通过 while 循环对数字 n 的每一位进行处理。一个整数的位数大约为 O(log₁₀(n))，所以该方法的时间复杂度为 O(log n)。

  • 空间复杂度：
    方法中只用了几个局部变量，没有额外的数据结构，因此空间复杂度为 O(1)。

isHappy 方法

  • 时间复杂度：
    isHappy 方法使用了快慢指针来进行循环检测。注意：

    • 对于任意正整数 n，通过 getNext 的转换，数字会迅速下降。实际上，经过一到两次 getNext 调用后，数值会降到几百以内，之后整个过程都在一个常数范围内循环。
    • 因此，虽然每次调用 getNext 的成本是 O(log n)（最初 n 较大时），但实际循环中的迭代次数是常数级的。
      综合来看，isHappy 的总时间复杂度为 O(log n)。

  • 空间复杂度：
    该方法只使用了少量额外的变量（slowRunner、fastRunner 等），所以空间复杂度为 O(1)。

总结：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

这种分析依赖于这样一个事实：数字经过几次平方和转换后，很快就降到了一个较小的常数范围内，从而使得循环迭代次数可以看作常数级别。

  • 时间复杂度： O(log⁡n)O(\log n) 。该分析建立在对前一种方法的分析的基础上（常数次循环），但是这次我们需要跟踪两个指针而不是一个指针来分析， 以及在它们相遇前需要绕着这个循环走多少次。
    • 如果没有循环，那么快跑者将先到达 1，慢跑者将到达链表中的一半。我们知道最坏的情况下，成本是 O(2⋅log⁡n)=O(log⁡n)O(2 \cdot \log n)=O(\log n) 。
    • 一旦两个指针都在循环中，在每个循环中，快跑者将离慢跑者更近一步。一旦快跑者落后慢跑者一步，他们就会在下一步相遇。 假设偱环中有 kk 个数字。如果他们的起点是相隔 k−1k-1 的位置（这是他们可以开始的最远的距离），那么快跑者需要 k−1k-1 步才能到达慢跑者， 这对于我们的目的来说也是不变的。因此，主操作仍然在计算起始 nn 的下一个值，即 O(log⁡n)O(\log n) 。
  • 空间复杂度： O(1)O(1) ，对于这种方法，我们不需要哈希集来检测循环。指针需要常数的额外空间。

数学

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

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

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

class Solution {

    // 用于检测循环的哈希集合，这些数是已知的会形成循环的数
    private static Set<Integer> cycleMembers =
        new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));

    // 计算一个数字的每个位上的平方和
    public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10; // 获取最低位的数字
            n = n / 10; // 去掉最低位的数字
            totalSum += d * d; // 计算该位的平方并累加到总和中
        }
        return totalSum;
    }

    // 判断一个数字是否是快乐数
    public boolean isHappy(int n) {
        // 当 n 不是 1 且不在已知的循环数集合中时，不断计算下一个数字
        while (n != 1 && !cycleMembers.contains(n)) {
            n = getNext(n); // 计算下一个数字
        }
        // 如果 n 变成了 1，说明是快乐数，否则不是
        return n == 1;
    }
}