LeetCode 0202 Happy Number
文章目录
LeetCode 0202 Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example:
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
思路1
- 获取每位数字,计算平方和
- 使用哈希表记录,如不存在添加,若存在说明存在循环,退出,到达最后的结果1也退出
时间复杂度 $O(log N)$ 空间复杂度 $O(log N)$
代码1
class Solution {
public:
bool isHappy(int n) {
if(n < 1) return false;
unordered_set<int> s;
while(n != 1 && !s.count(n))
{
s.insert(n);
int new_n = 0;
while(n)
{
int t = n % 10;
new_n += t * t;
n /= 10;
}
n = new_n;
}
return n == 1;
}
};
思路2
弗洛伊德循环查找算法: 隐式链表检测是否有环
- 跟踪两个值,称为快跑者和慢跑者。在算法的每一步中,慢速在链表中前进 1 个节点,快跑者前进 2 个节点(对
getNext(n)函数的嵌套调用)。 - 如果
n是一个快乐数,即没有循环,那么快跑者最终会比慢跑者先到达数字 1。 - 如果
n不是一个快乐的数字,那么最终快跑者和慢跑者将在同一个数字上相遇。
时间复杂度 $O(logN)$ 空间复杂度 $O(1)$
代码2
class Solution {
public:
int next(int n)
{
int ans = 0;
while(n)
{
int t = n%10;
ans += t * t;
n /= 10;
}
return ans;
}
bool isHappy(int n) {
int slow = n;
int fast = next(n);
while(fast != 1 && slow != fast)
{
slow = next(slow);
fast = next(next(fast));
}
return fast == 1;
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论