【蓝桥杯】每天一题，理解逻辑（3/90）【Leetcode 快乐数】

闲话系列：每日一题，秃头有我，Hello！！！！！,我是IF‘Maxue，欢迎大佬们来参观我写的蓝桥杯系列，我好久没有更新博客了，因为up猪我寒假用自己的劳动换了台新电脑，没用父母的钱哦！！！，虽然进度慢了，但是值得，蓝桥杯快开始了，所以我也开始努力起来了。同时，我也欢迎各位大佬互三，看到我会及时回复的！！！

放一张阿刃在这，除大家的霉运

题目解析

1. 搞懂定义

• 对于一个正整数，每一次替换为它每个位置上的平方和。

• 举例：

• 

  • 19这个数字经过处理可以变成1，2这个数字变成了无限循环，
  • 所以19是快乐数字，2就不是
  • 判断最后的那一个环是否都是一

算法原理解析

我们仔细观察，在最后的结尾，

• 为快乐数的数字最后的结尾都是1，我们可以理解成一个园环。

• 非快乐数的数字最后结尾我们知道，肯定不是1，但是因为鸽巢原理我们会得出结论肯定成环。（不知道也没关系，下面有详细解析）

• 原理如图所示，上面的是快乐数，下面的数是非快乐数：

  

• 判断最后的环的数字是否都是1.

具体解法

• 解法 快慢双指针。

  • 定义快慢指针

    • 慢指针每次后移一步，快指针每次后移两步 让慢指针一次进行一次操作，让快指针进行2次快乐数操作

    • 判断相遇的值

    • 直接判断相遇的值

• 鸽巢原理详解：
  • 我们可是让慢指针执行一次，然后对于快指针每一次后移进行执行快乐数的两次操作

    • 为什么这些数字不会一直铺开，为什么一定要成环？

      证明原理：鸽巢原理

    • 如果有n个巢，n+1个鸽子可以推论

    • 

      证明这道题：

    • 一个数字2.1 * 10^9

      

      • 我们已经知道n个巢穴，n+1个鸽子，如果鸽子全部归位，至少有一个巢穴里面的鸽子大于1.
      • 我们拿出9999999999这个数字，进行快乐数操作，
      • 范围将会锁定在【1，810（9^2 * 10）】 （这个就是巢穴） ，我们进行811次快乐数字操作（ 这个就是鸽子）

代码实现

int HappyC(int n)//快乐数的操作

{   int x=0;

int sum=0;

  while(n)

    {

    x=n%10;

    sum=x*x+sum;

    n=n/10;

    }

    return sum;

}

  

bool isHappy(int n) {

    //定义两个快慢指针，用数字代替

        int fast=0;

        int slow=0;

     slow=n,fast=n;

  while(1)

  {

    fast=HappyC(fast);

    fast=HappyC(fast);

    slow=HappyC(slow);

    if(fast==slow)

    {

        if(fast==1)

        {

            return true;

        }

        else

        {

            return false;

        }

    }

  }

  

}

运行结果展示：