【蓝桥杯】每天一题，理解逻辑（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;}}}}

运行结果展示：