清明連假第一天,題目很應景的出 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;
}
}
};
再度打完收工,繼續動森無人島隔離 🌴🌴🌴