快乐数原题地址
方法一:哈希集合
定义函数getNext(n),返回n的所有位的平方和。一直执行n=getNext(n),最终只有2种可能:
- n停留在1。
- 无限循环且不为1。
证明:情况1是存在的,如力扣的示例一:
接下来只需证明,反复执行getNext操作,最终一定会无限循环(停留在1可以理解为无限的1->1循环)。
分类讨论:
- n的位数小于等于3,那么getNext(n)<=getNext(999)=243,那么反复执行getNext(n),执行244次以上,根据抽屉原理,一定会出现循环。
- n的位数大于3,如n为4位数,执行getNext(n)后,n的位数会减小,直到变为情况1。
所以,我们可以使用如下算法:反复执行n=getNext(n),会出现下面3种情况:
- n=1,说明原来的n是快乐数。
- n不在哈希表中,则把n插入哈希表。
- n在哈希表中,且n≠1,说明n已经进入循环,原来的n不是快乐数。
// 方法一:哈希集合
class Solution {
// 计算n的所有位的平方和
int getNext(int n)
{
int sum = 0;
while (n)
{
int digit = n % 10;
n /= 10;
sum += (digit * digit);
}
return sum;
}
public:
bool isHappy(int n) {
unordered_set<int> hashtable;
while (n != 1)
{
// 若哈希表中没有n,就添加n,否则不是快乐数
if (!hashtable.count(n))
{
hashtable.insert(n);
}
else
{
return false;
}
n = getNext(n);
}
return true;
}
};
方法二:快慢指针(龟兔赛跑、弗洛伊德循环查找算法)
考虑到反复执行n=getNext(n),一定会进入循环,参考判断链表是否带环的思路,定义fast和slow,slow每次执行slow=getNext(slow)一次,fast每次执行fast=getNext(fast)两次,那么slow和fast最终一定会在循环内相遇。若相遇时slow=fast=1,则n为快乐数,否则不是快乐数。
这是因为若链表带环,最终fast和slow一定会入环,且每次fast比slow多走一步,fast和slow的距离缩短一步,最终距离一定会减为0,两者相遇。
// 方法二:快慢指针法
class Solution {
// 计算n的所有位的平方和
int getNext(int n)
{
int sum = 0;
while (n)
{
int digit = n % 10;
n /= 10;
sum += (digit * digit);
}
return sum;
}
public:
bool isHappy(int n) {
int slow = n;
int fast = getNext(slow);
while (slow != fast)
{
// 慢指针一次走一步
slow = getNext(slow);
// 快指针一次走两步
fast = getNext(getNext(fast));
}
return slow == 1;
}
};
方法三:数学
根据方法一所述,反复执行n=getNext(n),n一定会跌为三位数以下,且进入循环。使用硬编码穷举,最终的循环一定是...,4,16,37,58,89,145,42,20,4,...或者...1...
所以只需要提前把循环中的数存储在哈希表中,反复执行n=getNext(n),会出现3种情况:
- n在哈希表中,说明已经进入循环,原来的n不是快乐数。
- n=1,说明原来的n是快乐数。
- n不在哈希表中。
// 方法三:数学
class Solution {
// 计算n的所有位的平方和
int getNext(int n)
{
int sum = 0;
while (n)
{
int digit = n % 10;
n /= 10;
sum += (digit * digit);
}
return sum;
}
public:
bool isHappy(int n) {
while (1)
{
// 最终要么为1,要么进入循环
if (n == 1)
{
return true;
}
else if (cycleMembers.count(n))
{
return false;
}
n = getNext(n);
}
}
private:
static unordered_set<int> cycleMembers;
};
unordered_set<int> Solution::cycleMembers = { 4,16,37,58,89,145,42,20 };