双指针 之 快乐数
2024-01-09 09:42:40
目录
思路:根据题意,不管是否为快乐数,最终都会进入循环,所以可使用快慢指针的思想来解决此题
题目出处202. 快乐数 - 力扣(LeetCode)
思路:根据题意,不管是否为快乐数,最终都会进入循环,所以可使用快慢指针的思想来解决此题
示例一画图:
实例二画图:
代码:
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 ]的值,并进入循环。
文章来源:https://blog.csdn.net/handsomeliu18/article/details/135470776
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!