怎么查网站备案的公司,wordpress 无刷新评论,建设能播放视频的网站,html网页设计代码简单例子题目链接
力扣网202 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为#xff1a;
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1#xff0c;也可能是 无限循环 但始终变不…题目链接
力扣网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那么至少有一个鸽巢中会有多于一个鸽子。
在数学上鸽巢原理的一般形式是如果有 n1 个对象被放入 n 个容器中那么至少有一个容器中会包含两个或更多的对象。
鸽巢原理的应用范围广泛包括组合数学、概率论、计算机科学等领域。它可以用于解决各种问题如证明存在性、推理、计数等。
鸽巢原理的应用举例 1. 在一周的七天里如果有八个人生日那么至少有两个人生日在同一天。 2. 在一台有 30 个存储单元的计算机中如果有 31 个数据需要存储那么至少有两个数据会存储在同一存储单元中。
基于鸽巢原理我们来证明一下这道题的任意数据是必定带环的。
这道题数据的取值范围是2的31次方-1转换一下等于2147483647我们取到数字个数的最大值即9999999999可以推导出这个数通过题目的方法取到的数一定是最大的因为原数比范围还大同时也是各位上的最大值即81*10810所以测试样例的变化范围就在【1810】之间不会有大于它的数存在。
设需要检测的数为x假设最坏情况它变化了810次都没有重复的数存在说明它已经将1——810的数已经遍历完一遍当进行第811次时必定有重复值出现。
可以将1——810看成鸽巢x的变化次数为鸽子。
