🐤初次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
bool isHappy(int n) {
vector<int> res;
int count = 0;
while(n != 1 && count != 10) {
++count;
helper(n, res);
n = 0;
for(auto x: res) {
n += pow(x, 2);
}
}
if(count == 10)
return false;
return true;
}
void helper(int n, vector<int>& res) {
res.clear();
while(n) {
res.push_back(n % 10);
n /= 10;
}
}
};
|
🐤改进一
改用set来存储得到的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
bool isHappy(int n) {
while(n != -1) {
n = helper(n);
if(n == 1)
return true;
}
return false;
}
int helper(int n) {
int tl = 0;
while(n) {
tl += pow(n % 10, 2);
n /= 10;
}
if(!st.count(tl)) {
st.insert(tl);
return tl;
}
return -1;
}
private:
set<int> st;
};
|
🐤改进二
改用链表中查找是否有环的快慢指针思想来实现。
这里必然存在循环，快指针会追上慢指针。如果是快乐数，那么最后两个指针都会得到结果1；如果不是快乐数，那么两个指针在循环中也是会相遇的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool isHappy(int n) {
int fast = n, slow = n;
do {
slow = helper(slow);
fast = helper(fast);
fast = helper(fast);
} while(fast != slow);
if(fast == 1)
return true;
return false;
}
int helper(int n) {
int tl = 0;
while(n) {
tl += pow(n % 10, 2);
n /= 10;
}
return tl;
}
};
|
Accepted
401/401 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 83.82 % of cpp submissions (8 MB)
