欢迎来到CILMY23的博客
????本篇主题为：双指针算法之202. 快乐数 --- 快慢双指针（力扣）
????个人主页：CILMY23-****博客
????系列专栏：Python | C++ | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题 | 代码训练营
????感谢观看，支持的可以给个一键三连，点赞关注+收藏。
题目：
202. 快乐数 - 力扣（LeetCode）
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
一、题目解析
通过题目可以看到要求：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
首先，我们要求一个正整数的平方和，其次要重复这个过程，最后判断这个过程结果是否为1，如果为1则为快乐数.
二、算法原理
重点是过程的推断，我们得实际看看例题中的两个数， 在分别重复这两个过程后是什么情况。
首先是19的过程：
19不断经过这个过程，最终会在1中无限循环下去
接下来我们看2的过程：
2不断经过第一个过程，最终会在4这个圈中无限循环下去。因此，为了判断类似环的问题，我们曾经在链表中学过一个思想 ---- 快慢双指针
快慢双指针：
1.定义两个指针，一个为slow，每次走一步，一个为fast，每次走两步
2.如果在环内，那么这两个指针最终都会相遇
那现在，无论是上述哪种情况，都会形成一个环，这个环内的值不一样而已，一个全是1，一个绕回来不是1，所以判断相遇的值是不是1就可以判断是不是快乐数了。
三、代码编写
class Solution
{
public:
//计算平方和
int Num_Sum(int n)
{
int i = n % 10;
int sum = 0;
while(n)
{
i = n%10;
sum += i*i;
n = n/10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n;
int fast = Num_Sum(n);
while(slow != fast)
{
slow = Num_Sum(slow);
fast = Num_Sum(Num_Sum(fast));
}
return slow == 1;
}
};四、扩展---链表当中的快慢双指针
快慢指针是一种解决链表问题的重要技巧。在单链表中设置两个指针，一个快速移动（快指针），一个慢速移动（慢指针），可以有效地解决诸如寻找链表中环的起始节点、寻找链表中倒数第k个节点等常见问题。
一、快慢指针的基本原理
快慢指针的基本原理是利用双指针在链表中同时移动，快指针每次移动两步，慢指针每次移动一步。这样，当快指针到达链表尾部时，慢指针刚好指向链表中的一个节点。此时，我们可以利用慢指针回溯，找到环的起始节点或者倒数第k个节点。
二、应用场景
- 寻找链表中环的起始节点
当链表中存在环时，我们可以使用快慢指针来找到环的起始节点。首先，让快慢指针同时从链表头部开始移动。当它们相遇时，将快指针重新置为头部，然后继续移动。当快指针再次追上慢指针时，它所指的节点就是环的起始节点。 - 寻找链表中倒数第k个节点
我们可以使用快慢指针来找到链表中倒数第k个节点。首先，让快指针和慢指针同时从链表头部开始移动，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表尾部时，慢指针刚好指向倒数第k个节点。
????️感谢各位同伴的支持，本期C++就讲解到这啦，如果你觉得写的不错的话，可以给个一键三连，点赞，关注+收藏，若有不足，欢迎各位在评论区讨论。
注：扩展来自：快慢指针：解决链表问题的利器-百度开发者中心 (baidu.com)