双指针 之 快乐数

2024-01-09 09:42:40

目录

题目出处202. 快乐数 - 力扣(LeetCode)

思路:根据题意,不管是否为快乐数,最终都会进入循环,所以可使用快慢指针的思想来解决此题

代码:

补充:最后都会进入循环的原因,使用鸽巢原理证明


题目出处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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。