202. 快乐数
编写一个算法来判断一个数 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 <= n <= 231 - 1
哈希
首先想到的就是哈希和双指针嘛，那就先拿哈希试一下。
class Solution {public boolean isHappy(int n) {Set<Integer> hash = new HashSet<>();//只要n不等于1且hash中不存在这个数，就开始循环，否则跳出循环while(n!=1&&!hash.contains(n)){hash.add(n);n=nextNumber(n);}return 1==n;}//首先，对于每个n都要一直循环得到它的下一个数字，/*输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1*///所以，新设置一个函数得到下一个数字public int nextNumber(int n) {int sum = 0;while (n > 0) {int d = n % 10;n = n / 10;sum += d * d;}return sum;}}
效果一般，用哈希太慢了。
我们发现每次都要得到下一个数字，存在一个递归的行为。
接着看了一下输出的量级也不大，试一下递归。
递归
class Solution {//如果要用递归的话，我们需要把哈希表放在外面//不然每一次递归都在进行初始化哈希表HashSet<Integer> hash = new HashSet<>();public boolean isHappy(int n) {//为1的时候直接返回trueif(1==n){return true;}//哈希中有有这个数的时候就该退出了（说明进入了环）if(hash.contains(n)){return false;}//接下来是递归的操作//直接存进哈希中hash.add(n);int sum=0;while(0!=n){//求和int tmp = n%10;sum+=tmp*tmp;n/=10;}return isHappy(sum);}
}
双指针
class Solution {//快慢指针//slow每次前进一格，fast每次前进2格//如果成环，则fast总会追上slow，所以跳出循环//如果终点是1，则fast会一直停留在终点直到slow追上//我们在循环中加入判断，当fast到1时，直接返回truepublic boolean isHappy(int n) {int slow = n;int fast=getNext(n);while(fast!=1&&slow!=fast){slow = getNext(slow);fast=getNext(getNext(fast));if(fast==1) return true;}return 1==fast;}public int getNext(int n){int sum=0;while(n>0){int tmp = n%10;sum+=tmp*tmp;n/=10;}return sum;}
}
yeah！完结
