【双指针算法】快乐数

1.题目解析

2.算法分析

由图可知，不管是最后可以变成1的还是不可以变成1的都相当于形成环了，只是成环处值不一样

问题转变成，判断链表是否有环

采用双指针，快慢指针算法

• 1.定义快慢指针
• 2.慢指针每次向后移动一步，快指针一次相后移动两步
• 3.判断相遇时的值即可

证明：为什么一定会成环?

解答：这里用到了鸽巢原理（抽屉原理）：N个巢穴，N+1只鸽子，那么可以得知至少有一个巢里面的鸽子数大于1

int类型的数据最大为2.1e9，再大一点则为10个9，9999999999，共9^2*10=810，则进行811次运算必然会回到之前的,数

3.代码编写

class Solution {public boolean isHappy(int n) {int slow=n,fast=bitsum(n);while(fast!=slow){slow=bitsum(slow);fast=bitsum(bitsum(fast));}if(slow==1){return true;}else{return false;}}public int bitsum(int n){int sum=0;while(n!=0){int k=n%10;sum+=k*k;n=n/10;}return sum;}
}