每日一题：LeetCode-202.快乐数（一点都不快乐）

每日一题系列（day 06）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，日日累积，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️

题目：

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

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

示例：

在这里插入图片描述

提示：

1 <= n <= 2^31 - 1

思路：

虽然力扣把这题给标为了简单，但是如果你想不明白给的第二个条件，这题和困难也相差无二，第一个条件是给你一个正整数，每个位置的平方和就是下一个位置，第二个条件其实说明了在这里只有两种情况，一种是最后变成1一直循环，另外一种情况是存在一个环使得这个数永远不能为1。是1就快乐数，不是1就不是快乐数。

我知道你还有疑问：“为什么就这两种情况呢？循环会不会是无限不相等的循环？”

在这里插入图片描述

可以看到，当为2时就是一个循环，当为19时最后就能得到1，所以19为快乐数，2不是快乐数，但是最让人不快乐的地方在于会不会存在无限不循环？

在这里插入图片描述

上面也就说明了，我们快乐数只用两种情况，一种是最后为1一直循环，一种是其他数绕圈子循环，并不存在不循环的情况。

我们知道了题目是什么意思，那我们该如何写这个题目呢？
1、其实我们仔细观察不难发现，给了我们一个数，我们就一定能推出来下一个数，而下一个数就一定能推出来下下个数…而且所推的数是固定的不变的，这种关系是不是就像我们的链表关系？

2、所以这题其实我们就可以用链表来实现，给我们的每个值就是一个个节点，我们得到下一个数的方式其实也就是指针指向的关系。
3、我们前面得出了结论：如果最后循环为1就是快乐数，如果最后循环不为1就不是快乐数，说到循环和链表你能想到什么？没错————带环链表，还记得我们是如何解决带环链表的问题的吗？没错，我们使用的是双指针法来解决带环链表的问题。
4、这样就好办了，我们只需要设置快慢指针，如果快指针已经为1了，则就是快乐数，所以只要快指针不为1我们就一直循环，如果快指针与慢指针相遇了，这时我们就要判断快指针与慢指针的时的值是不是为1，如果不是1，则表示进入了我们所说的第二种情况，进入了其他数的循环，则就不为快乐数，直接返回false即可。

代码实现：

class Solution {
public:

    int GetNext(int x)//获得下一个数
    {
        int tmp = 0, cnt = 0;
        while(x)
        {
            tmp = x % 10;
            cnt += tmp * tmp;
            x /= 10;
        }
        return cnt;
    }
    bool isHappy(int n) {//传入的n值即为第一个节点
        int quick = n, slow = n;//让两个指针都指向第一个节点
        while(quick != 1)//当快指针没有变成1的时候一直循环
        {
            quick = GetNext(GetNext(quick));//用平方和的关系得到下一个数（链表指向的下一个值）快指针为2个数，所以调用两次
            slow = GetNext(slow);//慢指针一次一个数
            if(quick == slow && slow != 1) return false;//当两个指针相遇的时候，
        }
        return true;
    }
};