当前位置：首页 > news >正文

leetcode刷题日记——快乐数

news 2025/8/29 17:56:28

[ 题目描述 ]：
在这里插入图片描述
[ 思路 ]：

快乐数就是对一个正整数，不断将其替换为它各个位上数字的平方和，如果最终这个过程能够收敛到1，则这个数被称为快乐数。
如果不能收敛到1，则不是快乐数
拿 2 举个例子，2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 →…，最后变成一个无限循环
即是快乐数，则其结果含有1，非快乐数结果无限循环，且结果中不含1，
那么这个问题其实可以转换为判断生成的数据中，是否存在环，且环中值不为1
那么，可以使用快慢指针去判断是否存在环

int get_next(int n){int sum=0;while(n!=0){int num=n%10;n/=10;sum+=pow(num,2);}return sum;
}
bool isHappy(int n) {int fast=n;do{fast=get_next(fast);fast=get_next(fast);n=get_next(n);}while(fast!=n);return n==1;
}

根据上面的思想，那么我们可以存取每次运算的结果，如果出现重复的结果，且结果中没有 1，则说明不是快乐数
运行如下

int get_next(int n){int sum=0;while(n!=0){int num=n%10;n/=10;sum+=pow(num,2);}return sum;
}bool isHappy(int n) {int len=1;int* nums=(int*)malloc(sizeof(int)*len);nums[0]=n;while(n!=1){n=get_next(n);for(int i=0;i<len;i++){if(nums[i]==n){free(nums);return false;}}nums=(int*)realloc(nums,sizeof(int)*(len+1));nums[len++]=n;}free(nums);return true;
}

[ 官方题解 ]：

方法一：用 hash 检测循环，和上面第二个思路一样

def isHappy(self, n: int) -> bool:def get_next(n):total_sum = 0while n > 0:n, digit = divmod(n, 10)total_sum += digit ** 2return total_sumseen = set()while n != 1 and n not in seen:seen.add(n)n = get_next(n)return n == 1