力扣202. 快樂數

202. 快樂數 - 力扣（LeetCode）

難度 簡單

編寫一個算法來判斷一個數?n?是不是快樂數。

「快樂數」?定義為：

• 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
• 然后重復這個過程直到這個數變為 1，也可能是?無限循環?但始終變不到 1。
• 如果這個過程?結果為?1，那么這個數就是快樂數。

如果?n?是?快樂數?就返回?true?；不是，則返回?false?。

示例 1：

輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

輸入：n = 2
輸出：false

提示：

• 1 <= n <= 23^1 - 1

class Solution {
public:bool isHappy(int n) {}
};

---

解析代碼

類似判斷環形鏈表的快慢指針，了解一下鴿巢原理：

看一下環形鏈表的講解：

數據結構與算法⑥(第二章OJ題，下)后八道鏈表面試題-CSDN博客

此題為什么一定會成環？：

此題中最大范圍為23^1 - 1 等于?2.1*10^9 小于?9999999999（10個9）-> 每個數平方后為為9^2 * 10 = 810，所以超過810次每個數平方后，至少會有兩個數落在[1,810]，此時成環的時候slow等于1就是快樂數。

代碼：

class Solution {
public:int bitSum(int n){int sum = 0;while(n){int x  = n % 10;sum += x*x;n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast  = bitSum(n);while(slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}
};