力扣 202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例：
解析：
这道题主要看第二个条件：重复第一个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
一个快乐数19 -> 82 -> 68 -> 100 -> 1.
对于一个非快乐数他的平方和序列会陷入一个循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。
情况1：这个数循环执行，过程1要么就变变变，变成1。
情况2：这个数不是快乐数，循环执行过程1，变变变，一直变不成1，且进入到一个循环里面，在循环里一直转圈。
我们可以把这两种情况都归类为一种情况。
情况一也是情况2的一种：19 -> 82 -> 68 -> 100 -> 1 -> 1 -> 1 -> 1…。
不过它最后执行循环的都是1。
可以把它抽象想想成如下图所示
我们把循环部分抽象想像成环，之后再只需要判断这个环里的数据是否为1即可，如果不为1，那就是非快乐数。
那么我们首先要判断该结构是否有环状结构。
可以用快慢双指针的思路来解决。
那么解法就是：
- 定义快慢指针
- 慢指针每次向后移动一步，快指针每次走两步。
- 因为快乐数一定会相遇，相遇点肯定就在环形结构中，只需要判断相遇点是否唯一即可。
我们在此题上把双指针的抽象思路具体为把数看成指针：
slow = fast = 2；
slow走一步：
slow执行一次过程1。slow = 2 -> slow = 4;
fast走两步：
fast执行两次过程1。fast = 2 -> fast = 4 -> fast = 16;
补充：
没有条件2这种只有：1和无限循环这样的限制
该题还会有第三种情况：会一直往后走，永远不会重复，不会形成环结构。
但是其实第三种情况是永远不可能出现的。
代码实现：
int bitSum(int n)//返回这个数每一位上的平方和{int sum = 0;while(n){int t = n % 10;sum += t * t;n /= 10;}return sum;}
bool isHappy(int n) {int slow = n, fast = bitSum(n);while(slow != fast){slow = bitSum(slow);fast = bitSum( bitSum(fast));}//相遇之后只需判断相遇位置的值即可return slow == 1;}
