題目：
編寫一個(gè)算法來判斷一個(gè)數(shù)是不是 “快樂數(shù)”滔岳。
一個(gè) “快樂數(shù)” 定義為：對(duì)于一個(gè)正整數(shù)挽牢，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和禽拔，然后重復(fù)這個(gè)過程直到這個(gè)數(shù)變?yōu)?1室叉，也可能是無限循環(huán)但始終變不到 1硫惕。如果可以變?yōu)?1，那么這個(gè)數(shù)就是快樂數(shù)恼除。
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.
示例:
輸入: 19
輸出: true
解釋:
1^2+ 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
解題思路：
? 求每個(gè)位上的數(shù)字平方和豁辉，判斷是否為 1令野，如果不為 1 則繼續(xù)求該數(shù)每位的平方和。
如例題中求和：19 -> 82 -> 68 ->100 ->1 ->1 -> 1 ......
不管是否為快樂數(shù)徽级，該數(shù)最終必定進(jìn)入一個(gè)循環(huán)气破。進(jìn)入循環(huán)體的入口結(jié)點(diǎn)數(shù)字為 1灰追，則該數(shù)為快樂數(shù)，否則不是快樂數(shù)朴下。所以這道題就變成了 求有環(huán)鏈表的入環(huán)節(jié)點(diǎn)苦蒿，這類似之前做過的另一道題：環(huán)形鏈表 2
同樣，可以用 環(huán)形鏈表2 中的兩種方法找到入環(huán)節(jié)點(diǎn)团滥。
其實(shí)快樂數(shù)有一個(gè)已被證實(shí)的規(guī)律：
? 不快樂數(shù)的數(shù)位平方和計(jì)算报强，最后都會(huì)進(jìn)入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循環(huán)體。
所以該題可以用遞歸來解秉溉，基線條件為 n < =4，滿足基線體條件時(shí)父晶，如果 n=1 則原數(shù)為快樂數(shù)弄跌，否則不是。
哈希表解題：
Java：
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> hashSet = new LinkedHashSet<>();//哈希表記錄數(shù)位平方和計(jì)算過程中的每個(gè)數(shù)
while (!hashSet.contains(n)) {
hashSet.add(n);
int sum = 0;
while (n > 0) {//計(jì)算數(shù)位平方和
sum += (n % 10) * (n % 10);
n /= 10;
}
n = sum;//n 為數(shù)位平方和
}
return n == 1;
}
}
Python：
class Solution:
def isHappy(self, n: int) -> bool:
hashSet = set(1) #哈希集合內(nèi)置1埠胖，可減少一次循環(huán)
while n not in hashSet:
hashSet.add(n)
n = sum(int(i)**2 for i in str(n)) #py可以直接轉(zhuǎn)乘字符串遍歷每個(gè)字符計(jì)算
return n == 1
遞歸解題：
Java：
class Solution {
public boolean isHappy(int n) {
if (n <= 4) return n == 1;//基線條件
int sum = n, tmp = 0;
while (sum > 0) {
tmp += (sum % 10) * (sum % 10);
sum /= 10;
}
return isHappy(tmp);//遞歸調(diào)用
}
}
Python：
class Solution:
def isHappy(self, n: int) -> bool:
return self.isHappy(sum(int(i)**2 for i in str(n))) if n > 4 else n == 1 #一行尾遞歸
快慢指針解題：
**Java: **
class Solution {
public boolean isHappy(int n) {
int slow = n, fast = helper(n);
while (slow != fast) {//條件是快慢指針不相遇
slow = helper(slow);
fast = helper(fast);
fast = helper(fast);//快指針一次走兩步（計(jì)算兩次）
}
return slow == 1;
}
private int helper(int n) {//計(jì)算數(shù)位平方和輔助函數(shù)
int sum = 0;
while (n > 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
}
Python
class Solution:
def isHappy(self, n: int) -> bool:
slow, fast = n, self.helper(n)
while slow != fast:
slow = self.helper(slow)
fast = self.helper(fast)
fast = self.helper(fast)
return slow == 1
def helper(self, n: int) -> int:
return sum(int(i)**2 for i in str(n))
tips：
? 就這道題而言押袍，應(yīng)該用快慢指針的方法。雖然不管是否為快樂數(shù)最終都會(huì)進(jìn)入循環(huán)體汽馋，但是計(jì)算數(shù)位和的過程得到的每個(gè)數(shù)總量 理論上是可以非常大的圈盔，這就可能導(dǎo)致存儲(chǔ)的哈希集合長(zhǎng)度過大或遞歸深度太深，空間復(fù)雜度不可預(yù)測(cè)（不會(huì)超過整型范圍）驱敲≈谡＃快慢指針解題，每次值保存兩個(gè)值娩梨，空間復(fù)雜度為 1。
歡迎關(guān)注微.信.公.眾.號(hào)：愛寫B(tài)ug
