一.題目描述

202. 快樂數(shù) - 力扣（LeetCode）

二.題目解析

我們要判斷一個(gè)數(shù)是不是快樂數(shù)要通過它的三個(gè)性質(zhì)來進(jìn)行判斷。這個(gè)數(shù)會(huì)一直變化，由它的各個(gè)位的平方和重新構(gòu)成這個(gè)數(shù)。如果這個(gè)數(shù)在變化的過程中變成了1，那么就是快樂數(shù)；如果陷入了循環(huán)，一直變不到1，就說明不是快樂數(shù)。

?所以，對于一個(gè)數(shù)n來說有兩種情況：1、在進(jìn)行若干次變換后變成了1；2、在進(jìn)行若干次變換之后進(jìn)入了循環(huán)。

但其實(shí)，我們可以將第一種也歸為是進(jìn)入循環(huán)的一種，只不過每一個(gè)位置都是1.

三.算法原理?

我們看到上面的情況圖有沒有聯(lián)想到之前學(xué)習(xí)鏈表的一道題——帶環(huán)鏈表。判斷一個(gè)鏈表是否帶環(huán)，我們利用了快慢雙指針。這里我們也可以使用快慢指針來實(shí)現(xiàn)：

這里其實(shí)是在模擬帶環(huán)鏈表的性質(zhì)。我們讓slow每次變換一次，fast變換兩次即可。

擴(kuò)展：

這道題之所以簡單是因?yàn)轭}目已經(jīng)告訴我們一定會(huì)進(jìn)行循環(huán)，但是如果沒有這句話呢？有沒有可能n一直變換下去，不會(huì)進(jìn)入循環(huán)？

答案是不會(huì)的！

四.代碼實(shí)現(xiàn)

因?yàn)槲覀冃枰l繁求一個(gè)數(shù)的每個(gè)位的平方和，所以我們將其寫成一個(gè)函數(shù)。

int getSquare(int n)
{int ans = 0;while (n){int index = n % 10;ans += index * index;n /= 10;}return ans;
}bool isHappy(int n)
{int slow = n;int fast = getSquare(n);while (fast != slow){slow = getSquare(slow);fast = getSquare(getSquare(fast));}return slow == 1;
}