LeetCode - 解题笔记 -202- Happy Number
Solution 1
整个题需要做两件事情：
- 按数位拆分，并计算平方和
- 根据屡次变换结果寻找是否存在循环
至于是否循环或到达1是唯二的两种情形，已经在官方题解中快乐数 - 快乐数 - 力扣（LeetCode）给出了详细分析，不再赘述。
第一个部分，直接使用模拟思路即可；第二部分，可以使用 0142. Linked List Cycle II 中的快慢指针思路，而且平方和计算的演化路径唯一确定，可以不使用额外的保存空间处理之。
- 时间复杂度： O ( log N ) O(\log N) O(logN)，其中 N N N为输入的数字，按数位处理的整个演化路径是对数复杂度，而其上的循环判定为 O ( 2 log N ) O(2 \log N) O(2logN)
- 空间复杂度： O ( 1 ) O(1) O(1)，仅维护常数个状态量
class Solution {
public:
bool isHappy(int n) {
int slow = n;
int fast = n;
while (fast != 1) {
slow = number(slow);
fast = number(number(fast));
if (slow == fast) { break; }
}
return fast == 1;
}
private:
int number(int now) {
int sum = 0;
while (now > 0) {
int part = now % 10;
now = now / 10;
sum += pow(part, 2);
}
return sum;
}
};
Solution 2
Solution 1的Python实现
class Solution:
def isHappy(self, n: int) -> bool:
def number(now: int) -> int:
ret = 0
while now > 0:
part = now % 10
now = now // 10
ret += pow(part, 2)
return ret
slow = n
fast = n
while fast != 1:
slow = number(slow)
fast = number(number(fast))
if slow == fast: break
return fast == 1