您當前位置：首頁 > php開源 > 綜合技術 > LeetCode筆記：202. Happy Number

LeetCode筆記：202. Happy Number

來源：程序員人生發布時間：2016-11-24 08:48:39 閱讀次數：2661次

問題：

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: 19 is a happy number

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

大意：

寫1個算法來判斷1個數字是不是“happy”。
1個happy數字是通過下面的進程來辨別的：從1個正整數開始，用其各位數字的平方和來代替它，然后重復這個進程直到數字等于1（此時就保持不變了），或它會1直循環而不等于1。那些得到1的數字就是happy的數字。
距離：19是1個happy數字
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路：

1看到這個題目我是懵逼的，看1個數字是否是happy，出題人真有童心。想找規律吧算了幾個數字感覺沒得規律找啊。從最簡單的思路來看就是不斷循環看最后得到的是否是1了，但是返回true的判斷容易，甚么時候就能夠下結論說這個數字不happy呢？這才是問題。首先我們得到的數不知道是幾位數，但是經過計算后最后肯定會變成個位數，而如果這個個位數是1那就是happy了，如果不是1應當就是不happy吧。所以我1開始的做法是循環求平方和，直到結果是個位數了就看是否是1來給出結果，這里還用到了1個遞歸，如果計算1次平方和還不是個位數就繼續遞歸計算。
提交后發現有個毛病，那就是1111111這個數，也是1個happy數字，但我判斷為不是了。我數了1下1共7個1，平方和是7，才知道原來到了個位數后還會繼續計算，我算了1下發現7還真能最后算出1來，那只能對1~99個個位數都看看是否是能算出1來了，算了1下覺得太麻煩了，因而想到了1個簡單的方法，leetcode是可以自定義測試用例的，勾選Custom Testcase就能夠了，然后我把4~9都試了1遍，不用試2、3是由于就等于4、9，測完發現只有1和7是的，所以在代碼里把7也算成true就能夠了。
最后的時間是4ms，還不錯，看了看discuss也沒有看到特別好的方法，那大抵就是這樣了吧。

代碼（Java）：

public class Solution {
    public boolean isHappy(int n) {
        int sum = 0;
        while (n > 0) {
            sum += Math.pow((n % 10), 2);
            n = n / 10;
        }
        if (sum >= 10) return isHappy(sum);
        else if (sum == 1 || sum == 7) return true;
        else return false;
    }
}