一.題目描述

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

二.題目解析

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

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

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

三.算法原理?

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

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

擴展：

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

答案是不會的！

四.代碼實現(xiàn)

因為我們需要頻繁求一個數(shù)的每個位的平方和，所以我們將其寫成一個函數(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;
}