LeetCode Happy Number（快樂數）

       在每天枯燥的算法練習中我們應該保持怎樣的心情呢，當然是快樂哈，那麼今天給大家介紹一下什麼是快樂數（還是算法、哈哈）~

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.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1             

       這道題定義了一種快樂數，就是說對于某一個正整數，如果對其各個位上的數字分别平方，然後再加起來得到一個新的數字，再進行同樣的操作，如果最終結果變成了1，則說明是快樂數，如果一直循環但不是1的話，就不是快樂數，那麼現在任意給我們一個正整數，讓我們判斷這個數是不是快樂數，題目中給的例子19是快樂數，那麼我們來看一個不是快樂數的情況，比如數字11有如下的計算過程：

1^2 + 1^2 = 2                    2^2 = 4                              4^2 = 16

1^2 + 6^2 = 37                  3^2 + 7^2 = 58                 5^2 + 8^2 = 89

8^2 + 9^2 = 145                1^2 + 4^2 + 5^2 = 42      4^2 + 2^2 = 20                2^2 + 0^2 = 4

       我們發現在算到最後時數字4又出現了，那麼之後的數字又都會重複之前的順序，這個循環中不包含1，那麼數字11不是一個快樂數，發現了規律後就要考慮怎麼用代碼來實作，我們可以用set來記錄所有出現過的數字，然後每出現一個新數字，在set中查找看是否存在，若不存在則加入表中，若存在則跳出循環，并且判斷此數是否為1，若為1傳回true，不為1傳回false。下面是我的Java實作：

public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<Integer>();
        while(n!=1){
            int sum = 0;
            while(n>0){
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            if(set.contains(sum)){
                return false;
            } else {
                set.add(sum);
            }
            n = sum;
        }
        return true;
    }
           

       其實這道題也可以不用set來做，我們并不需要太多的額外空間，關于非快樂數有個特點，循環的數字中必定會有4，這裡我就不證明了，大家可以多拿幾個數試試其實挺有意思的，比如5,14等都會回到4，是以也就有了下面的實作：

public boolean isHappy(int n) {    

    while (n != 1 && n != 4) {
            int t = 0;
            while (n) {
                t += (n % 10) * (n % 10);
                n /= 10;
            }
            n = t;
        }
        return n == 1;
    }
           

       通過這道題主要還是想鍛煉大家邏輯思維能力的，還有就是對集合類的靈活應用，另外想告訴大家有些題目是比較有規律的，我們在解決一個問題時應該把視野放的更廣一些，當我們找到規律的呢一刻，我們就可以倍數級的縮短我們解決問題的代碼複雜度了。最後呢還是希望大家都可以把程式設計作為一種樂趣，快樂的刷題哦~