双指针 之 快乐数

目录

题目出处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 ]的值，并进入循环。