清明連假第一天,題目很應景的出 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;
        }
    }
};

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

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料