Leetcode — 202. Happy Number (中文)

問題連結: https://leetcode.com/problems/happy-number/

題目求我們回傳給予數字n 是否為happy number
以下為happy number 定義-

• 給定一個任一正整數n, 並把n轉換成 其所有位數的平方和
• 重複上述的動作直到我們發現n可以轉換成1 或者直到我們發現 n只能循環地轉換成各種不是1的數字
• 當n可以轉換成1的時候 代表他就是happy number

範例
Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0²

想法:

從happy number的定義, 其實讓我們可以蠻直觀的寫出要如何找出給予數字n的所有位數數字的平方和
我們只要用一個loop, 每個loop中, 用除法和其餘數來找目前最後一個位數的數字及捨棄最後一個數字, 往下找倒數第二個位數的數字

比如給予數字123, 我們可以用 123 除 10 的餘數, 來取得最後一位數的數字, 因為我們用完3了, 再把123/10的結果 就可以把3捨棄掉

因此 我們可以寫出下面的helper method來找要取代n的下一個數字是多少

public int helper(int n){
        int sum = 0;
        while(n>0)
        {
            int lastDigit = n%10;
            sum += lastDigit*lastDigit;
            n/=10; //abandon the last digit
        }
        return sum;
    }

我們會不停地呼叫helper method直到我們發現n可以轉變成1 或者我們發現我們一直不停地重覆在繞幾個非1的數字 (也就是一直循環了)

所以現在的問題就是 — 我們要如何知道我們已重複在找一樣的數字?

最簡單的方法就是用一個集合來存所有我們找過的數字, 如果我們發現我們已經把這個數字傳進helper method過了, 代表如果我們繼續下去的話, 我們就會開始重複我們上次傳進去那個數字後找過的所有數字了, 因此我們在發現有重複數字時,就直接回傳false 代表我們無法找到1

以下為 1ms程式碼, 贏過 84% — (以下呼叫的helper method就是我們上面提到的)

public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n>0)
        {
            n = helper(n);
            if(n==1)
                return true;
            if(set.contains(n))
                return false;
            set.add(n);
        }
        return false;
    }

而如果你練習過這題 141. Linked List Cycle , 你會發現其實這兩題的概念十分相像! 沒錯, 我們這題也可以用兩個pointers來幫忙我們找cycle!

1. slow — 每次都只呼叫一次helper method的結果
2. fast — 每次都呼叫兩次helper method的結果

當我們發現slow 和 fast 指向的結果是相同的時候, 代表我們已經進入循環了

以下為 0ms程式碼, 贏過 100% — (以下呼叫的helper method就是我們上面提到的)

public boolean isHappy(int n) {
        int slow = n, fast = n;
        while(slow!=1 || fast!=1)
        {
            slow = helper(slow);
            fast = helper(helper(fast));
            if(slow==1 || fast==1)
                return true;
            if(slow==fast)
                return false;
        }
        return true;
    }