建设部网站上标准合同,免费的app软件大全,网站建设团队成员,wordpress被和谐目录
题目介绍#xff1a; 算法原理#xff1a;
鸽巢原理#xff1a;
如何找到环里元素#xff1a;
代码实现#xff1a; 题目介绍#xff1a;
题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09; 算法原理#xff1a;
我先简单举两个例子#xff…目录
题目介绍 算法原理
鸽巢原理
如何找到环里元素
代码实现 题目介绍
题目链接. - 力扣LeetCode 算法原理
我先简单举两个例子
19 2 其实大部分人拿到这道题第一感觉就是如果是快乐数只需利用循环一步步求解最后如果有一次结果为1时就是快乐数可是如果不是快乐数岂不是要一直循环下去这道题最重要的一点就是如果不是快乐数最后的数据是必定成环的证明需要利用鸽巢原理
鸽巢原理
如果有n个巢穴n1只鸽子那么必定会有一个巢血有2个或以上的鸽子。
这个原理很简单我们利用它来证明一下这道题若不是快乐数必定成环
利用极限法
来看看这道题数据的最大值2的31次方2147483648不妨再去大点直接取9999999999我们看看这个数经历一次变化替换为该数每一位的平方和后会变成多少也就是9*9*10810这个最大的数经历一次变化后变为810那么比这个数小的数经历一次变化肯定不会大于810所以我们的巢就是1-810也就是有810个巢那我们的鸽子就是变化的次数一个数若变化811次则至少有2个数是重复的重复的一出现后面就全一样了就成环了。 那如果是快乐数是不是就没有环呢其实也有快乐数最后变为1后若再经历一次变化还是1其实也成环了只是环里的元素都是1而不是快乐数环里的元素都不是1所以这道题目的思路很清晰了我们只要找到一个环里元素判断是不是1就行了。
如何找到环里元素 面对这种环的问题我们可以利用双指针里的快慢指针法就可以求解了如图 slow慢指针一次走一步fast快指针一次走两步。
还没进环之前slow永远无法追上fast指针但当进环后就像两个人在圆形跑道比赛只要两人有速度差速度不一样就绝对会相遇。 只要以相遇判断相遇时的元素是否为1就行。
代码实现
class Solution {
public:int compute(int n)//计算n每个位上的平方和{int sum0;while(n){int tmp n%10;sumtmp*tmp;n/10;}return sum;}bool isHappy(int n) {int slow n,fastcompute(n);//初始fast在slow前一个while(slow!fast){slowcompute(slow);//slow一次走一步fastcompute(compute(fast));//fast一次走两步}return fast1;//相遇时fast或者slow等于1就是快乐数}
};
