LeetCode 快乐数2020-10-19 620 words, 2 minutes to read 题目描述 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。 示例: 输入: 19 输出: true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 解题思路 方法一:龟兔赛跑(C语言 O(1)) 这道题其实就是包装后的环形链表,其中 慢指针就是每次把数字各位求一次平方和 快指针就是每次把数字各位求两次平方和 有两种情况 是快乐数:最后两个指针都会变成1,重合在一起 不是快乐数:相当于一个环,快慢指针总会在某个数处相遇 即:不管是不是快乐数,快慢指针最终都会汇聚到一个数上,我们只需要判断这个数是不是1即可 int nextNumber(int n){ int res=0; while(n!=0){ res+=(n%10)*(n%10);//求平方和 n/=10; } return res; } bool isHappy(int n){ //快慢指针在同一起点 int slow=n;//慢指针(乌龟) int fast=n;//快指针(兔子) do{ slow=nextNumber(slow);//慢指针走 1 步 fast=nextNumber(nextNumber(fast));//快指针走 2 步 }while(slow!=fast); return fast==1; }