LC 202.快乐数

本文主要是介绍LC 202.快乐数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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\le n\le 2^{31}-1$

解法一(Set哈希+模拟)

思路分析：

1. 对于一个正整数n，判断其是否为快乐数，我们可以模拟对于快乐数的定义，通过定义来判断一个数是否为快乐数

2. 同时假设一个数组116，在反复通过平方和计算下一个数字时，会得到58，然后经过一段运算后，58还会再次出现，由于回到了一个已经计算过的数字，因此可以发现这个过程存在一个循环，永远也不会回到1，即返回false

3. 所以可以猜测有以下三种可能

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

4. 第三种情况可以推导不会发生(例举每一位数的最大数字的下一位数)

5. 因此对于算法主要分为两部分：

   1. 对于一个数字，计算它的下一个数字
   2. 根据算出来的一系列数字判断是否进入了循环

6. 对于第一部分，按照定义模拟即可，至于第二部分，使用哈希集合(HashSet)来完成，每生成一个数字，检查它是否在已知的哈希集合中

   1. 如果在哈希集合中，则说明处于一个循环，返回false
   2. 如果不在哈希集合中，可以继续推导，并将该数字加入到集合中

实现代码如下：

class Solution {public boolean isHappy(int n) {HashSet<Integer> hashSet = new HashSet<>();        // 哈希集合 记录计算得到的数字判断是否进入循环int x = n;while (x != 1) {if (hashSet.contains(x)) {    // 如若集合中存在该数 则进入循环 返回falsereturn false;} else {hashSet.add(x);        // 集合中不含有该元素 则保存该元素到集合中// 计算下一位int t = 0;while (x != 0) {int y = x % 10;t += y * y;x /= 10;}x = t;    // 更新下一位判断的数值}}return true;}
}

复杂度分析：

• 时间复杂度：$O(lo{g}^n)$
• 空间复杂度：$O(lo{g}^n)$

解法二(快慢双指针)

思路分析：

1. 对于推导正整数n是否为快乐数得一系列过程中，所产生得一系列数可以构成一个隐式链表，并且将快乐数的最后结果1放在链表末尾。
2. 那么对于不快乐数的反复运算，会反复出现的系列数字 便构成了隐式链表中的环
3. 因此可以将快乐数问题转换为 判断隐式链表是否有环的问题
4. 那么如何判断链表是否有环，可以使用弗洛伊德查找算法，即快慢双指针法
   1. 快指针每次走两步，慢指针每次走一步
   2. 若存在环 则快指针一定能追上慢指针 即两个指针一定会相遇
5. 当两个指针相遇时，退出循环，若值为1则说明是快乐数，若值不为1则说明不是快乐数

实现代码如下：

class Solution {public boolean isHappy(int n) {int fast = n;    // 快指针int slow = n;    // 慢指针do {// 快指针移动fast = bitSquareSum(fast);fast = bitSquareSum(fast);// 慢指针移动slow = bitSquareSum(slow);} while(fast != slow);return slow == 1;    // 判断相遇时 是否为1}// 获取一个数的各个位上的 数的平方和public int bitSquareSum(int x) {int sum = 0;while (x != 0) {int t = x % 10;sum += t * t;x /= 10;}return sum;}
}

提交结果如下：

解答成功:执行耗时:0 ms,击败了100.00% 的Java用户内存消耗:38.9 MB,击败了14.59% 的Java用户

复杂度分析：

• 时间复杂度：$O(lo{g}^2)$
• 空间复杂度：$O(1)$

解法三(面试不推荐)(数学+模拟)

思路分析：

1. 因为HashMap的查询、插入等操作需要耗费不少时间，因此考虑尝试直接暴力模拟进行求解
2. 百度搜索快乐数得，若该数不为快乐数，则在反复计算中会陷入一个循环4→16→37→58→89→145→42→20→44，因此只要计算过程中出现数字4，那么直接返回false即可

实现代码如下：

class Solution {public boolean isHappy(int n) {if (n == 1) {return true;}int num = n;while(num != 1) {// 计算各个位 数的平方和int sum = 0;while (num != 0) {int x = num % 10;sum += x * x;num /= 10;}num = sum;if (num == 4) {return false;}}return true;}
}

提交结果如下：

解答成功:执行耗时:0 ms,击败了100.00% 的Java用户内存消耗:38.7 MB,击败了27.83% 的Java用户

复杂度分析：

• 时间复杂度：$O(lo{g}^n)$，n指可能需要重复定义运算的次数，m则是每次循环得到的数的位数
• 空间复杂度：$O(1)$

这篇关于LC 202.快乐数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---