目录
思路:根据题意,不管是否为快乐数,最终都会进入循环,所以可使用快慢指针的思想来解决此题
示例一画图:
实例二画图:
class Solution {
public:
int SquareSum(int n)//计算所有位的平方和
{
int sum = 0;
while(n)
{
int i = n % 10;
sum += i * i;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n;
int fast = SquareSum(n);
while(slow != fast)//快慢指针,快指针一次走两步,慢指针走一步
{
slow = SquareSum(slow);
fast = SquareSum(SquareSum(fast));
}
return slow == 1;
}
};
题目的输入值范围是
那我们不妨在大胆放大一下,认为取值范围是 [ 1,?9999999999 ],远远大于题目给的范围,方便下面证明
9999999999第一次取每位的平方和一定是最大的,这个不难理解,算得为810,根据鸽巢原理,之后的所有平方和都小于等于810,所以最小第811次,一定会再次得到[ 0,? 810 ]的值,并进入循环。