快乐数--快慢指针（判断成环思路）

0x01.问题

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2= 1

public boolean isHappy(int n)

0x02.解决思路

读题，发现题目要点：

• 判断一个数，经过一系列【每一次将该数替换为它每个位置上的数字的平方和】操作，是否可以变成1。

问题其实很简单，只需要不断的模拟这个过程变换就可以了，但是，在里面会存在一些问题。

如果它永远不会变成1，那么它会怎样变换呢？

一种想法是，它会越来越大，越来越大，最后会超出整型的范围，但是我们可以拿个具体的例子看一下。

• 三位数经过这个操作能得到的最大的数字是999—>243，四位数是9999—>324。

• 再来看一下接近整型的大数9999999999999—>1053。

我们发现，其实并不会大到超出整型的范围，而是会在一个很小的范围内变换
，那么在这个小范围的变换就只有两种情况了。

1. 最后变成1。
2. 不断循环。

第一种情况是我们需要的，我们只需要判断是否出现循环就行了，如果出现了循环，并且还没有得到1，说明之后是不可能再得到1了的。

如何判断是否出现循环了呢？很简单，只需要判断当次得到的数是否已经出现过就行了。那么我们可以使用一个哈希表存储一下每次得到的数，如果当次得到的数已经出现过了，那么直接返回false。

class Solution {
    private int next(int n){
        int ans=0;
        while(n>0){
            int d=n%10;
            n/=10;
            ans+=d*d;
        }
        return ans;
    }
    public boolean isHappy(int n) {
        Set<Integer> hash=new HashSet<>();
        while(n!=1&&!hash.contains(n)){
            hash.add(n);
            n=next(n);
        }
        return n==1;
    }
}

这种方法是最简单，最直接的。

其实，判断是否出现循环，还有另外一种常用的方法，快慢指针，跟判断链表是否成环思路一样。

0x03.解决代码–快慢指针

class Solution {
    private int next(int n){
        int ans=0;
        while(n>0){
            int d=n%10;
            n/=10;
            ans+=d*d;
        }
        return ans;
    }
    public boolean isHappy(int n) {
        int slow=n;
        int fast=next(n);
        while(fast!=1&&fast!=slow){
            slow=next(slow);
            fast=next(next(fast));
        }
        return fast==1;
    }
}

ATFWUS --Writing By 2020–04-30