文件上传并返回查看地址
939 2023-04-03 04:26:39
https://leetcode.cn/problems/happy-number/
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ;不是,则返回 false 。
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
1 <= n <= 231 - 1
可以采用哈希来存储,或者快慢指针。无限循环的话,可以当做一个环,如果不是环,那么就收敛于1.对于求是否存在环,用快慢指针,一个走两步,一个走一步,相遇或到1为止。
时间复杂度 O(n)空间复杂度 O(1)
Java
public boolean isHappy(int n) { int slow = n; int fast = get(n); while (fast != 1 && fast != slow) { fast = get(get(fast)); slow = get(slow); } if (fast == 1) { return true; } else { return false; } } public int get(int n) { int sum = 0; while (n > 9) { int d = n % 10; n = n / 10; sum += d * d; } sum += n * n; return sum; }