题目链接
力扣网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的变化次数为鸽子。