C语言每日一题（64）快乐数

题目链接

力扣网202 快乐数

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

思路分析

知识点：双指针、快慢指针

解析：

从题目开始分析，第一句话，对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。没什么好说的，很简单；第二句话：然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1，什么意思？

我们看示例1，你看着它的运算过程，发现它最终等于1，是快乐数，

但示例2没有运算过程，直接输出false，就不好分析为什么错误，那我们用上面的方法对他进行一下运算看看。

当我们把过程中出现的每一个数用画图的形式表现出来时，我们发现，2开头，最后从4开始进入循环，很想以前我们做过的判断带环链表，所以可以用快慢指针法来改进一下

环形链表详解

方法步骤

1.定义两个快慢指针，但此指针非比指针，而是每个阶段的值，slow走一步，fast走两步。

当它们相遇时，再判断其中一值是否为1即可。

代码

（建议自己去实现一下再看会比较好）

int bitsum(int n) {//求各位上的数的平方和
    int sum = 0;
    while (n) {
        int j = n % 10;
        sum += j * j;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int fast = n, slow = n;
    do {
        slow = bitsum(slow);
        fast = bitsum(bitsum(fast));
    } while (slow != fast);
    return slow == 1;
}

拓展

在前面我们漏了一个关键点没有考虑，就是这个方法实现的基础是这段数据组成的链表（逻辑上）是有环的，我们怎么肯定这段数据是带环的呢？

这里介绍一个数学原理：鸽巢原理

鸽巢原理，也被称为抽屉原理、鸽笼原理，是一种基本的计数原理，用来描述在一定条件下的排列组合问题。

鸽巢原理的形象解释是：如果有 n 个鸽子被放入 m 个鸽巢中，其中 n > m，那么至少有一个鸽巢中会有多于一个鸽子。

在数学上，鸽巢原理的一般形式是：如果有 n+1 个对象被放入 n 个容器中，那么至少有一个容器中会包含两个或更多的对象。

鸽巢原理的应用范围广泛，包括组合数学、概率论、计算机科学等领域。它可以用于解决各种问题，如证明存在性、推理、计数等。

鸽巢原理的应用举例：

1. 在一周的七天里，如果有八个人生日，那么至少有两个人生日在同一天。
2. 在一台有 30 个存储单元的计算机中，如果有 31 个数据需要存储，那么至少有两个数据会存储在同一存储单元中。

基于鸽巢原理，我们来证明一下这道题的任意数据是必定带环的。

这道题数据的取值范围是2的31次方-1，转换一下等于2147483647，我们取到数字个数的最大值，即9999999999，可以推导出，这个数通过题目的方法取到的数，一定是最大的（因为原数比范围还大，同时也是各位上的最大值），即81*10=810，所以，测试样例的变化范围就在【1，810】之间，不会有大于它的数存在。

设需要检测的数为x，假设最坏情况，它变化了810次都没有重复的数存在，说明它已经将1——810的数已经遍历完一遍，当进行第811次时，必定有重复值出现。

可以将1——810看成鸽巢，x的变化次数为鸽子。