算法训练——day16快乐数

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