30-Day LeetCoding Challenge (Day2)

清明連假第一天，題目很應景的出 202. Happy Number：判斷一個數字是不是 Happy Number。

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

而怎樣叫做 Happy number：就是這個數字不斷的用自己的各位數平方相加來取代，直到最後會等於 1；
或是會進入一個不斷重複的 Loop 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，這種就是 Unhappy number。

👉 https://zh.wikipedia.org/wiki/%E5%BF%AB%E6%A8%82%E6%95%B8
👉 https://www.stem.org.uk/news-and-views/opinions/how-find-happy-number

［ Happy Number ］

［ Unhappy Number ］

所以一開始最基本的哈扣暴力解，就出現了

static int __ = [](){std::ios::sync_with_stdio(false); return 0;}();

class Solution {
public:
    bool isHappy(int n) {
        int temp = 0;

        while(true) {
            while(n > 0){
                temp += pow(n % 10, 2);
                n /= 10;
            }

            if(temp == 1)
                return true;
            else if(temp == 4   ||
                    temp == 16  ||
                    temp == 37  ||
                    temp == 58  ||
                    temp == 89  ||
                    temp == 145 ||
                    temp == 42  ||
                    temp == 20)
                return false;
            else {
                n = temp;
                temp = 0;
            }
        }
    }
};

不過中途遇到 WA，小小 debug 一下發現原來是誤把 sqrt 當成 pow 了（汗
👉 平方 http://www.cplusplus.com/reference/cmath/pow/
👉 根號 http://www.cplusplus.com/reference/cmath/sqrt/

但仔細想想哈扣實在是太 low，換一個寫法把出現過的都存起來，直接從裡面找，反正 loop 就會重複出現(笑

static int __ = [](){std::ios::sync_with_stdio(false); return 0;}();

class Solution {
public:
    bool isHappy(int n) {
        vector<int> v;
        
        while(true) {

            int temp = 0;
            while(n > 0){
                temp += pow(n % 10, 2);
                n /= 10;
            }

            if(temp == 1)
                return true;

            auto it = find(v.begin(),v.end(), temp);
            if(it != v.end())
                return false;
            
            v.push_back(temp);
            n = temp;
        }
    }
};

再度打完收工，繼續動森無人島隔離 🌴🌴🌴