Leetcode-202-快乐数

Leetcode-202-Happy Number

思路：

题目描述

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

参考题解：https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/

方法一：哈希表

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

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

• 思考

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

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

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

Digits	Largest	Next
1	9	81
2	99	162
3	999	243
4	9999	324
13	9999999999999	1053

1. 对于三位数的数字，他不可能大于243。

（这意味着它要么被困在243以下的循环内，要么跌倒1。）

2. 对于4位或者以上的是数字，在每一步都会丢失一位，直到降到3位位置。所以我们知道，最坏的情况下，算法可能会在243以下的循环内或者回到1。但它不会无限期的进行下去，所以我们排除第三种选择。

• 算法
  • 给定一个数字n，判断他的下一个平方后数字是什么
  • 按照一系列数字来判断我们是否进入了一个循环

第 1 部分我们按照题目的要求做数位分离，求平方和。

第 2 部分可以使用 HashSet 完成。每次生成链中的下一个数字时，我们都会检查它是否已经在 HashSet 中。

• 如果不在hashset中，把它加入到hashset中
• 如果在hashset中，说明我们进入了一个循环，返回false。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();

        // 循环条件： 回到了1表示快乐数字 并且 这个数字之前没有出现过
        while (n != 1 && !set.contains(n)){
            // 加入到set中
            set.add(n);
            // n的下一个平方数
            n = getNext(n);
        }
        // 判断结果
        return n == 1;
    }

    // 计算n 的平方数函数
    private int getNext(int n) {
        int total = 0;

        while (n > 0){
            int d = n % 10;
            n = n / 10;
            total += d*d;
        }
        return total;
    }
}

复杂度分析：（这里参考官网）

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

时间复杂度：O(243 \cdot 3 + \log n + \log\log n + \log\log\log n)...O(243⋅3+logn+loglogn+logloglogn)... = O(logn)。
查找给定数字的下一个值的成本为 O(logn)，因为我们正在处理数字中的每位数字，而数字中的位数由 \log nlogn 给定。
要计算出总的时间复杂度，我们需要仔细考虑循环中有多少个数字，它们有多大。
我们在上面确定，一旦一个数字低于 243243，它就不可能回到 243243 以上。因此，我们就可以用 243243 以下最长循环的长度来代替 243243，不过，因为常数无论如何都无关紧要，所以我们不会担心它。
对于高于 243243 的 nn，我们需要考虑循环中每个数高于 243243 的成本。通过数学运算，我们可以证明在最坏的情况下，这些成本将是 O(\log n) + O(\log \log n) + O(\log \log \log n)...O(logn)+O(loglogn)+O(logloglogn)...。幸运的是，O(\log n)O(logn) 是占主导地位的部分，而其他部分相比之下都很小（总的来说，它们的总和小于\log nlogn），所以我们可以忽略它们。
空间复杂度：O(\log n)O(logn)。与时间复杂度密切相关的是衡量我们放入 HashSet 中的数字以及它们有多大的指标。对于足够大的 nn，大部分空间将由 nn 本身占用。我们可以很容易地优化到 O(243 \cdot 3) = O(1)O(243⋅3)=O(1)，方法是只保存集合中小于 243243 的数字，因为对于较高的数字，无论如何都不可能返回到它们。

方法二：快慢指针

• 通过反复调用getNext(n) 得到的是一个隐式的链表。

• 隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。

如果这里意识到实际上有个链表，那么可以转换成链表是否有环的问题

• 因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的快的称为 “乌龟”，跑得快的称为 “兔子”。

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

算法：

• 我们不是每次链表中的一个值，而是跟踪两个值，称为快跑者和慢跑者。
• 在每一步的算法中，慢速在链表中前进一个节点，快跑这前进两个节点。

打赏