LeetCode 202: 快乐数 Happy Number
题目：
编写一个算法来判断一个数是不是 “快乐数”。
一个 “快乐数” 定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
示例:
输入: 19 输出: true 解释: 1^2+ 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
解题思路：
求每个位上的数字平方和，判断是否为 1，如果不为 1 则继续求该数每位的平方和。
如例题中求和：19 -> 82 -> 68 ->100 ->1 ->1 -> 1 ……
不管是否为快乐数，该数最终必定进入一个循环。进入循环体的入口结点数字为 1，则该数为快乐数，否则不是快乐数。所以这道题就变成了 求有环链表的入环节点 ，这类似之前做过的另一道题：环形链表 2
同样，可以用 环形链表2 中的两种方法找到入环节点。
其实快乐数有一个已被证实的规律：
不快乐数的数位平方和计算，最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环体。
所以该题可以用递归来解，基线条件为 n < =4 ，满足基线体条件时，如果 n=1 则原数为快乐数，否则不是。
哈希表解题：
Java：
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> hashSet = new LinkedHashSet<>();//哈希表记录数位平方和计算过程中的每个数
while (!hashSet.contains(n)) {
hashSet.add(n);
int sum = 0;
while (n > 0) {//计算数位平方和
sum += (n % 10) * (n % 10);
n /= 10;
}
n = sum;//n 为数位平方和
}
return n == 1;
}
}
Python：
class Solution:
def isHappy(self, n: int) -> bool:
hashSet = set(1) #哈希集合内置1，可减少一次循环
while n not in hashSet:
hashSet.add(n)
n = sum(int(i)**2 for i in str(n)) #py可以直接转乘字符串遍历每个字符计算
return n == 1
递归解题：
Java：
class Solution {
public boolean isHappy(int n) {
if (n <= 4) return n == 1;//基线条件
int sum = n, tmp = 0;
while (sum > 0) {
tmp += (sum % 10) * (sum % 10);
sum /= 10;
}
return isHappy(tmp);//递归调用
}
}
Python：
class Solution:
def isHappy(self, n: int) -> bool:
return self.isHappy(sum(int(i)**2 for i in str(n))) if n > 4 else n == 1 #一行尾递归
快慢指针解题：
**Java: **
class Solution {
public boolean isHappy(int n) {
int slow = n, fast = helper(n);
while (slow != fast) {//条件是快慢指针不相遇
slow = helper(slow);
fast = helper(fast);
fast = helper(fast);//快指针一次走两步（计算两次）
}
return slow == 1;
}
private int helper(int n) {//计算数位平方和辅助函数
int sum = 0;
while (n > 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
}
Python
class Solution:
def isHappy(self, n: int) -> bool:
slow, fast = n, self.helper(n)
while slow != fast:
slow = self.helper(slow)
fast = self.helper(fast)
fast = self.helper(fast)
return slow == 1
def helper(self, n: int) -> int:
return sum(int(i)**2 for i in str(n))
tips：
就这道题而言，应该用快慢指针的方法。虽然不管是否为快乐数最终都会进入循环体，但是计算数位和的过程得到的每个数总量 理论上是可以非常大的，这就可能导致存储的哈希集合长度过大或递归深度太深，空间复杂度不可预测（不会超过整型范围）。快慢指针解题，每次值保存两个值，空间复杂度为 1。
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
