202.Happy Number 快乐数字

1. 题目详情

leetcode题目地址 (opens new window)

📗difficulty：Easy

🎯Tags：

• Two Pointers (opens new window)
• HashTable (opens new window)
• Math (opens new window)

题目描述：

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

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

样例：

输入: 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. 解题思路

在题目描述中有一个描述非常值得关注：也可能是无限循环但始终变不到 1 。

一种简单的思路是，如果检测到 1 ，那么可以停止。如果该数字一直计算下去，就会形成死循环。那么停止的循环处理的一个条件可以是：检测到一个死循环，就停止掉程序，这也是本题的突破口。

---

3. 优秀解答：

以下题解参考 leetcode-cn (opens new window) 官方题解

3.1 HashSet

📃帖子原址 (opens new window)

对这种看起来没有什么规律的问题，解决的思路是尝试手算，寻找规律。 直接思考难以发现有效的规律。

假设一个数字 7 ，按照题目的说明进行处理，最终得到的结果为 1，返回 true 。

假设一个数字为 116 ，最终会出现一个循环。

那么可以思考这样一个问题，对给定的一个数字，执行题目给定的操作，这个数字最终会无限大吗？这是很关键的一个问题。

这样可以将情况划分为如下三类：

1. 数字最终为 1，是快乐数字
2. 不断循环，例如 116 ，没有结束，不是快乐数字
3. 数字随着处理越来越大，最后趋于一个无穷大的数字。

对于最后一直情况，列举一些数字，去验证这个猜想。列出下面这个表格。

位数	最大值	求下一个数字
1	9	81
2	99	162
3	999	243
4	9999	324
13	9999999999999	1053

如果一个数字为 4 位以及以上的数字，那么最终会演化为 3 位数字，而这个 3 位数字，最大为 243 。

那么上面的猜想就不成立，只需要对 2 种情况进行分类处理就可以了。同时，可以确定的是，一个不是快乐数字的数字最终演化到循环状态是有限次的操作。

Hash 表查询 key 的时间复杂度为 O(1) , 利用这个性质可以实现常数级的查询操作。

核心代码：

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;
    }
}

复杂度分析:

3.2 ”快慢指针“ 法

📃帖子原址 (opens new window)

仔细观察一下下面给出的图片，是否发现这里可以看成是一个”链表“，当然这是一种隐性的链表。

而处理链表中的循环，一种很好的方法是快慢指针。一个指针移动 1 个步长，一个指针移动 2 个步长，如果存在循环，那么这 2 个快慢指针最终会相遇。在本题中，也就意味着循环的终结，这个数不是快乐数，返回 false 。

这种算法和学名叫： 弗洛伊德循环查找算法 。在 力扣中国 给出了更加详细的说明：

核心代码：

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);
        // 如果是快乐数字，那么演化到 1；fast 指针跑得快，计算后依旧为 1
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner)); // 2 倍步长
        }
        return fastRunner == 1;
    }
}

复杂度分析: