leetcode面试经典150题——50 快乐数

本文介绍: 同样的，我们出来可以利用哈希表来判断循环，还可以用快慢指针来判断循环，因为在一个循环中，快指针一定会追上慢指针，所以当我们快指针追上了慢指针时，就证明出现了循环，返回false，当没有循环的时候，快指针会比慢指针更加快的达到1，因此我们while循环的结束条件为快指针追上了慢指针或者快指针达到了1.以此类推，我们发现从三位数开始往后，其各位平方相加之和不可能大于这个数，所以我们对于任意一个数字，最后都不会变得无穷大，因此不存在出现第二种情况，所以对于一个不是快乐数的数字，一定会出现循环。

描述：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
leetcode链接

bool isHappy(int n) {
    unordered_set<int> set;
    while(n!=1&&!set.count(n)){//当n不等于1并且没有陷入循环的时候继续while循环
        set.insert(n);
        int sum = 0;
        while(n>0){
            int digit = n%10;
            sum+=digit*digit;
            n/=10;
        }
        n = sum;//更新n
    }
    return n==1;
}

bool isHappy(int n) {
    int slow = n,fast = n;
    do{
        fast = getNext(getNext(fast));//快指针一次前进2格
        slow = getNext(slow);//慢指针一次前进1格
    }while(fast!=slow&&fast!=1);
    return fast==1;
}
//求数字n的下一个数字
int getNext(int n){
    int sum = 0;
    while(n>0){
        int digit = n%10;
        sum+=digit*digit;
        n/=10;
    }
    return sum;
}