[leetCode]202. 快樂數

部落格園: https://www.cnblogs.com/PythonFCG/p/13870962.html

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

「快樂數」定義為：對于一個正整數，每一次将該數替換為它每個位置上的數字的平方和，然後重複這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。如果 可以變為 1，那麼這個數就是快樂數。

如果 n 是快樂數就傳回 True ；不是，則傳回 False 。

示例：

輸入：19

輸出：true

解釋：

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

哈希

這題的關鍵是要了解題目中的無線循環，這說明某個數字的位平方和會出現重複，是以可以使用哈希表判斷該數字是否重複，如果重複出現說明已經進入無限循環。如果數字位平方和為1則說明該數字是快樂數。

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        while (true) {
            int result = getBitSquareSum(n);
            if (result == 1) return true;
            if (set.contains(result)) {
                return false;
            }else {
                set.add(result);
            }
            n = result;
        }
    }

    private int getBitSquareSum(int num) {
        int sum = 0;
        while (num != 0) {
            sum += (num%10) * (num%10);
            num = num/10;
        }
        return sum;
    }
}