力扣算法题——202.快乐数【系统讲解】
目录
💕1.题目
💕2.解析思路
本题思路总览
借助 “环” 的概念探索规律
从规律到代码实现的转化
快慢指针的具体实现
代码整体流程
💕3.代码实现
💕4.完结
二十七步也能走完逆流河吗
💕1.题目
💕2.解析思路
本题思路总览
力扣 202 题 “快乐数” 要求判断一个给定的正整数是否为快乐数。快乐数的定义是：对于一个正整数，不断将该数替换为它每个位置上的数字的平方和，若最终结果能变为 1，则该数为快乐数；若陷入某个非 1 的循环，则不是快乐数。我们可以把数字在计算过程中的变化看作是在一个 “数字轨道” 上移动，而如果是快乐数，最终会进入一个值始终为 1 的 “环”。基于此，我们采用快慢指针的方法来检测是否进入了这样的 “环”，进而判断该数是否为快乐数。
借助 “环” 的概念探索规律
1. “数字轨道” 与 “环” 的形成
当我们对一个正整数不断计算其各位数字的平方和时，会得到一系列的数字，这些数字构成了一个 “数字轨道”。在这个过程中，可能会出现重复的数字，一旦出现重复，后续的计算就会陷入循环，形成一个 “环”。如果这个数是快乐数，那么最终会进入一个值始终为 1 的 “环”；如果不是快乐数，则会进入一个非 1 的 “环”。
2. 快慢指针检测 “环”
为了检测是否进入了 “环”，我们引入快慢指针。慢指针每次沿着 “数字轨道” 移动一步，即只进行一次各位数字平方和的计算；快指针每次移动两步，即进行两次各位数字平方和的计算。如果存在 “环”，快指针最终会追上慢指针，也就是它们的值会相等。
从规律到代码实现的转化
既然我们知道可以通过快慢指针来检测 “环”，并且能根据环的情况判断是否为快乐数，那么在代码中就可以直接使用快慢指针进行判断。快慢指针的移动规则和判断逻辑与上述规律一致，通过不断移动指针并比较它们的值，就能确定是否进入了 “环” 以及是否为快乐数。
快慢指针的具体实现
1. 快慢指针定义
slow：作为慢指针，每次只计算一次数字各位的平方和。fast：作为快指针，每次计算两次数字各位的平方和。
2. 指针移动规则
- 慢指针
slow：通过循环取出当前数字的每一位，计算其平方并累加，得到新的slow值。- 快指针
fast：先进行一次和慢指针类似的计算，得到一个中间结果，然后基于这个中间结果再进行一次同样的计算，完成两次计算过程。
3. 终止条件
在快慢指针移动过程中，不断检查它们的值是否相等。当
fast和slow相等时，说明进入了 “环”。此时判断它们的值是否为 1，如果为 1，则说明初始数字是快乐数；如果不为 1，则不是快乐数。
代码整体流程
1. 变量初始化
初始化输入数字
n的副本k，以及临时变量tep1、tep2用于存储每一位数字，还有快慢指针slow和fast初始化为 0。
2. 无限循环计算
在一个无限循环中，不断进行快慢指针的计算和判断。
- 计算慢指针
slow：通过取模和整除运算，依次取出n的每一位数字，计算其平方并累加到slow中，直到n变为 0。- 计算快指针
fast：先对k进行一次和慢指针类似的计算，然后将结果重新赋值给k，再进行一次同样的计算，完成两次计算。- 判断相遇情况：如果
fast和slow相等且都为 1，说明进入了值为 1 的 “环”，是快乐数，返回true；如果相等但不为 1，说明进入了非 1 的 “环”，不是快乐数，返回false。- 重置变量：将
n重置为slow，k重置为fast，并将slow和fast重置为 0，以便下一次计算。
通过以上步骤，我们就可以利用快慢指针准确判断一个给定的正整数是否为快乐数。
💕3.代码实现
class Solution { public: bool isHappy(int n) { int k = n; int tep1; int tep2; int slow = 0,fast = 0; while(1) { while(n>=1) { tep1 = n%10; n = n/10; slow += tep1*tep1; } while(k>=1) { tep2 = k%10; k = k/10; fast += tep2*tep2; } if(k == 0) { k = fast; fast = 0; } while(k>=1) { tep2 = k%10; k = k/10; fast += tep2*tep2; } if(fast == slow&&slow == 1) { return true; } if (fast == slow && slow != 1) { return false; } if(n == 0) { n = slow; slow = 0; } if(k == 0) { k = fast; fast = 0; } } } };
