LeetCode202 Happy Number

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

  • $1^2 + 9^2 = 82$
  • $8^2 + 2^2 = 68$
  • $6^2 + 8^2 = 100$
  • $1^2 + 0^2 + 0^2 = 1$

样例

1
2
3
4
Input:
19
Output:
true

思路

判断一个数是否是“happy”的。

“happy”的定义是每次将数$n$替换为其各数位的平方和,若最终得到1,则该数为“happy”。

如果一个数是“happy”的,可以直接模拟一遍,看是否得到1。但如果不是“happy”的话,那么模拟将陷入死循环,进入到一个不包含1的圈里。

这里介绍一个Floyd判圈算法,又称龟兔赛跑算法。该算法可以在有限状态机、迭代函数或者链表上判断是否存在环。如果从同一个起点(即使这个起点不在某个环上),同时开始以不同速度前进的两个指针最终相遇,那么可以判定存在一个环。

我们假设龟以1×的速度,兔以2×的速度从起点出发。若途中不存在圈,那么兔将率先到达终点。但是如果存在圈的话,龟兔便会在圈中相遇。此时兔必然是领先龟数圈,然后从后方追上龟。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
// 计算数位平方和
int cal(int n) {
int ans = 0;
while (n) {
ans += (n % 10) * (n % 10);
n /= 10;
}
return ans;
}
bool isHappy(int n) {
int fast = n, slow = n; // 相同起点
do {
slow = cal(slow); // 模拟龟,1×速度
fast = cal(cal(fast)); // 模拟兔,2×速度
} while (slow != fast); // 直到相遇
return slow == 1; // 为1则在终点相遇,否则在圈中相遇
}
};
分享到 评论