大庆开发网站公司,第一家中文商务网站,刚刚西安发布重要通知,wordpress网LeetCode原题链接#xff1a;202. 快乐数
下面是题目描述#xff1a;
「快乐数」 定义为#xff1a;
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1#xff0c;也可能是 无限循环 但始终变不到 1。 如果…LeetCode原题链接202. 快乐数
下面是题目描述
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 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的情况有没有可能不是循环但仍一直在变化呢
答案是不可能。运用鸽巢原理可以证明这一点。那么下面是简单的证明过程 先简单地说明一下鸽巢原理也就抽屉原理指的是有n个鸽巢n1个鸽子鸽子全部往巢中飞时至少有一个鸽巢中鸽子的数量是大于1的 接下来开始证明。由题目所给的数据范围我们可通过最大的一个数可以计算得到“鸽巢”的大小范围 231 - 1 2,147,483,647 经题目要求的计算方式计算一次可以得到一个数260。那么任意一个符合题目数据范围的数只会在[1, 260]这个区间内变化这个区间也就是“鸽巢”。也就是说只要一个正整数比 231 - 1 小它的变化只会在[1, 260]中极端来看一个数在变化了260次之后把n个鸽巢填满下一次变化也绝对会在这个范围中让某个鸽巢中鸽子的数量大于1因为那个数不管变成多少都一定比231 - 1 小。由此我们就无需担心一开始的那个问题。
2、解题思路 根据上面分析给定的正整数要么是无限循环要么最后变成1再通过对两个示例中算出来的数进行 “连接”会发现这个问题可以转换成为链表带环问题。如下图 所以可以直接按解决链表带环的问题方法解决本题。唯一需要变化的就是快慢指针的定义。链表带环问题中快指针一次走两步慢指针一次走一步在本题中快指针一次按要求计算两次慢指针按要求计算一次最后判断两个指针是否相遇即可。
3、具体代码
class Solution {
public:int calculate(int num){int sum 0;while(num){sum pow(num % 10, 2);num / 10;}return sum;}bool isHappy(int n) {int slow calculate(n);int fast calculate(calculate(n));while(slow ! 1 fast ! 1){if(slow fast){return false;}slow calculate(slow); //slow;fast calculate(calculate(fast)); //fast2;}return true;}
};看完觉得有觉得帮助的话不妨点赞收藏鼓励一下有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论多多指点谢谢朋友们
