快乐数
题目链接 202. 快乐数
编写一个算法来判断一个数
n是不是快乐数。「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果
n是 快乐数 就返回true；不是，则返回false。示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
题目解释
什么是快乐数,就是将我们数的每一位数计算他的平方,判断他是否是1,如果不是是1,我们持续上面的操作,直到我们遇到1,那么这个数就是快乐数.如果我们无法得到1,那么就是不快乐的.
算法原理
下面我们用两个例子来解析我们如何解决这道题目.
- val是快乐数
- val不是快乐数
我们发现,无论val是不是快乐数,我们都会陷入下面的情况.
这里很容易的想到我们在链表中判断是是否存在环.那么就可以使用快慢指针了.
- 快指针走2步
- 慢指针走1步
细节补充
- 快慢指针中快指针走2步,慢指针走1步为何可以判断有环,这里不再解释,可以看看链表相关的
- 我们上面经过若干次判断,难道一定会生成环的情况吗?不能是一条直线吗
- 如何快速转换val的值
如果我们分析了题目中的快乐数的第二条定义,那么我们可以隐约猜到一定会存在环.这里也是可以简单的说明一下.我们说下鸽巢原理
鸽巢原理一般含义为:如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素.
我们看一下我们的数据范围
- 1 <= n <= 2^31^ - 1
这里我们会发现,对于我们每一次的val经过转换,都会出现在[0, 810]的结果内,只要我们转换超过810次,那么一定会出现重复的元素.
解决我们如何一次的转换val的值,很简单,提取每一位的值,经过平方后保存下来
int bitSum(int val)
{
int sum = 0;
while (val)
{
int ret = val % 10;
sum += ret * ret;
val /= 10;
}
return sum;
}
代码编写
class Solution
{
public:
int bitSum(int val)
{
int sum = 0;
while (val)
{
int ret = val % 10;
sum += ret * ret;
val /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n;
int fast = n;
while (true)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
if (slow == fast)
break;
}
return slow == 1;
}
};