目录
1.题目
2.思路解析
3.代码展示
1.题目
. - 力扣(LeetCode)
2.思路解析
题目意思是将一个正整数上面的每一位拿出来,然后分别求平方,最后将这些数字的平方求和得到一个数字,如此循环,如果在此循环中得到了这个和为’1‘,那么就return true;反之false
我们任意取几个数字距离,发现可以得到如下规律
由图可知,这是一个有环链表,说起链表问题,在判断一个链表是否有环的时候,我们常用的思想就是快慢指针思想,通常来讲就是有两个指针slow和fast,slow初始化在第一个位置,fast初始化在第二个位置,slow一次走一格,fast一次走两格,如果slow指针可以和fast指针相遇,那么就说明这个链表是有环的。
我但是这一题并不是真正的链表,所以更准确的来讲我们使用“快慢指针的思想”去解决。
也就是说我们是要想办法模拟出快慢指针的行为模式。
如上图的数字是一个循环,所以我们首先需要去考虑的是如何去将这个类似于链表的“环”构造出来
如果我输入一个数字“2”,我应该如何得到“4”呢?,那么我首先需要的是一个将输入数字“2”的每个位子上的数字拆出来然后求和的函数,于是我们先写了下面的这样一个函数
之后我们需要考虑的是如何让这个循环动起来,自动构造一个环,然后让慢指针slow每次走一个格子,快指针fast每次走两个格子达成如图所示的效果
由于纯数字结构不可能去形成环,所以我们只能用“指针”去代表这环上面的每个元素,如图,slow初始化是slow=n,n是2,fast初始化就是对n使用了一下函数bitsum
如何让慢指针slow每次推进一格,我们只要调用一次函数bitsum既可以了
如何让快指针dfast每次推进两个格子,我们只要将fast目前所代表的数字调用一下bitsum得到它后面的一个数字,再让它后面的一格数字再次调用一下bitsum就可以了,这便是如下的代码。
3.代码展示
class Solution
{
public:
int bitsum(int n)
{
int sum=0;
while(n!=0)
{
int a=n%10;
sum=sum+a*a;
n/=10;
}
return sum;
}
bool isHappy(int n)
{
int slow=n;
int fast=bitsum(n);
while(fast!=slow)
{
slow=bitsum(slow);
fast=bitsum(bitsum(fast));
}
return slow==1;
}
};