☆打卡算法☆LeetCode 202. 快乐数 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

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

2、题目描述

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

「快乐数」 定义为：

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

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

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

示例 2：
输入： n = 2
输出： false

二、解题

1、思路分析

今天的题目是快乐数。

今天你快乐了吗？

题意要求我们判断一个数，是否是快乐数，每一次将该数替换为它每个位置上的数字的平方和，直到该数为1。

那么每个数字饿平方和指向另一个数字，所以是从任意数字进行平方和的迭代操作。

比如说数字7，下一个数字是49（7²），然后是97(4²+9²)，不断重复该过程，直到得到了1，那么这个7就是快乐数：

再举一个例子，116，通过反复平方和得到下一个数字，最终得到58之后就开始循环回到58，所以不可能到达1，因此116不是一个快乐数：

那么这个代码应该怎么实现呢：

• 求数字的平方和
• 根据一系列的数字判断是否进入了循环

判断是否进入循环其实也很简单，使用一个哈希表添加出现的数字，当数字再次出现就说明出现了循环。

2、代码实现

代码参考：

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、时间复杂度

时间复杂度：O(log n)

时间复杂度：O(243 · 3 + log n + log log n + log log log n)...=O(log n)

空间复杂度：O(log n)

衡量空间复杂度主要是看哈希集中中的数字以及它们有多大的指标。

对于足够大的n，大部分空间将有n本身占用 。

三、总结

快乐的知识点又增加了。

这是一道经典的链表找环的题目。

除了链表找环，更进一步的是 有向图找环。

相比于链表找环，每个点可能指向了多个其他的点。

有向图找环 比较经典的做法就是使用 深度优先搜索，从每个点出发，按有向图去游走，游走的时候记录当前走过的路径。如果在搜索的过程中遇到了曾经走过的路，那么就找到环了。