20200301：快樂數（leetcode202）

快樂數

• 題目
• 思路與算法
• 代碼實作

題目

思路與算法

1. 樓下太吵，刷個簡單的，這題本身沒有任何難點，非要說難點就在如何判斷這個數的各個位平方和會不會變成死循環，一直加下去，舉個例子：
2. 25，這個數往下加，29->85->89->145->42->20->4->16->37->58->89如此，這個89重複出現了，意味着進入了循環，是以我們隻需要判斷如何跳出循環即可，是以想到利用哈希表的資料唯一性來實作。
3. 方法二為大佬的快慢指針法，也列出來，非常nb的破除循環的方法。

代碼實作

方法一：哈希表解法

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        set.add(n);
        while(n > 1){
            n = bitSum(n);
            if(set.contains(n)){
                 return false;
            }  
            set.add(n);
        }
        return true;
    }
    // 擷取其逐位數字的平方和
    private int bitSum(int n){
        int sum = 0;
        int num;
        while(n != 0){
            num = n%10;
            n /= 10;
            sum += num*num;
        }
        return sum;
    }
}
           

方法二：快慢指針法

class Solution {
    public boolean isHappy(int n) {
       int fast,slow;
       fast = n;
       slow = n;
       // 此處需要先執行一次，是以使用do while
       do{
           slow = bitSum(slow);
           fast = bitSum(fast);
           fast = bitSum(fast);
       }while(slow != fast);
       return slow == 1;
    }


    // 擷取其逐位數字的平方和
    private static int bitSum(int n){
        int sum = 0;
        if(n == 0){
            return 0;
        }
        while (n > 0){
            int i = n % 10;
            sum += i*i ;
            n /= 10;
        }
        return sum;
    }
}