45.快乐数

题目

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

思路

• 快乐数的定义是基于一个计算过程，即对一个正整数，不断将其替换为它各个位上数字的平方和，如果最终这个过程能够收敛到1，则这个数被称为快乐数。

• 相反，如果在这个过程中形成了一个不包含1的循环，则该数不是快乐数。

• 对于非快乐数，它们的平方和序列会进入一个固定的循环，例如4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。

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

• 最终会得到 1。
• 最终会进入循环。
• 值会越来越大，最后接近无穷大(不会发生，因为假设9999999999999，那他每个位置的数值平方相加后的值是1053，再往后循环只会越来越小)。

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

• 对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。

• 4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。

• 所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。

方法一：哈希表检测

所以这道题的解法主要是两部分:

• 按照题目的要求做数位分离，求平方和。

• 使用哈希集合完成。每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。

  • 如果它不在哈希集合中，我们应该添加它。
  • 如果它在哈希集合中，这意味着我们处于一个循环中，因此应该返回 false。

class Solution {

    fun isHappy(n: Int): Boolean {
        val hasSet = HashSet<Int>()

        var next = n
        while (next != 1 && !hasSet.contains(next)) {
            hasSet.add(next)
            next = getNext(next)

        }
        return next == 1
    }

    fun getNext(n: Int): Int {
        var result = 0

        var num = n
        while (num > 0) {
            var a = num % 10
            num = num / 10
            result += a * a
        }
        return result
    }
}

class Solution {
    private 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) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

• 时间复杂度: O(Logn)
• 空间复杂度: O(Logn)

方法二：快慢指针法

通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。起始数字是链表的头 “节点”，链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。

意识到我们实际有个链表，那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的慢的称为 “乌龟”，跑得快的称为 “兔子”。

不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。

所以整体的思路就是快指针每次走两步，慢指针每次走一步。

class Solution {
    fun isHappy(n: Int): Boolean {
        var slow = n
        var fast = next(n)
        while (fast != 1 && slow != fast) {
            slow = next(slow)
            fast = next(next(fast))
        }
        return fast == 1
    }

    private fun next(n: Int): Int {
        var sum = 0
        var x = n
        while (x > 0) {
            val d = x % 10
            sum += d * d
            x /= 10
        }
        return sum
    }
}

class Solution {

     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) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
    }
}

复杂度分析:

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

• 空间复杂度：O(1)，对于这种方法，我们不需要哈希集来检测循环。指针需要常数的额外空间。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!