专题一_双指针_快乐数

一：题目解析

总结：

①：快乐数进行在某一次"对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和"操作后，是永远循环为1

②：非快乐数也是循环的

二：算法原理

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

        我们将这一步命名为bitsum函数

所以根据题目，我们知道快乐数，在某一次进行bitsum函数操作后会一直是1的循环，因为1进行bitsum永远是1 

但其实非快乐数也有自己的循环，如2，其的变化路径为：2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4   此时为4了形成循环

所以快乐数和非快乐数的区别就是，快乐数的循环中的每一个数字都是1，而非快乐数的循环的每一个数字都不是1 所以我们现在只需要判断，一个数进入循环后，是否为1即可！

问题是怎么判断一个数字进行bitsum的操作后，进入了循环？很简单，只需快慢指针的思路即可,因为只要成环，一个快一个慢，就一定会相遇，好比你跑步比一个人快，在操作这个环中，只要时间够久，则你一定会和跑步慢的人相遇！

所以一个slow就等于题目给的n，一个fast等于bitsum(n)，然后循环地进行slow走一步，fast走两步，则二者一定会在环中相遇！此时再判断相遇时的值是什么即可！

三：代码编写

class Solution {
public:int bitsum(int n){int sum = 0;while(n){sum += (n%10)*(n%10);//每个位置上数字的平方和n= n/10;//让下一次取到前一个位置是的数字}return sum;}bool isHappy(int n) {int slow = n, fast = bitsum(n);while(slow!=fast){//slow走一步slow = bitsum(slow);//fast走两步fast = bitsum(fast);fast = bitsum(fast);}return slow==1;}
};

Q：为什么你能保证非快乐数一定成环？

A：鸽巢原理，n个巢穴 n+1鸽子 所以至少一个巢穴的鸽子数大于1

首先题目的值的最大值为2^31次方-1 为：2,147,483,647，所以我们干脆直接将其记作9999999999，此时其已经是十位数的极限的 为什么我们要全取9？因为我想说明再大的值都适用于鸽巢原理，此时9999999999根据规则变成下一个数的时候 其实最大的数810

所以现在任何数字根据规则变成下一个数  下一个数的区间就是[1,810]
[1,810]就是巢穴 所以现在一个数字最多变810次 就一定会成环 甚至可能根本不会变这么多次就会成环；所以对于2,147,483,647来说，次数只会更少！