欢迎阅读 欢迎来到「快乐数」题解之旅本文将带你从“判断一个数在迭代平方和过程中是否会陷入循环”这一数学问题出发深入理解快慢指针Floyd判圈算法的经典应用并掌握如何高效检测循环而不必存储历史状态。在开始之前建议你先了解题目背景这是 LeetCode 202 题给定一个正整数 nn每次将其替换为各位数字的平方和重复这一过程若最终变为 1 则该数为快乐数否则会陷入不含 1 的循环。本质上这是一个检测链式变换是否进入循环的问题类似于判断链表是否有环。明确学习目标掌握两种解法——哈希集合存储历史值直观但需额外空间和快慢指针Floyd判圈算法空间 O(1)O(1)理解为什么平方和序列一定会进入循环值域有限以及快慢指针如何通过“每次慢走一步、快走两步”来检测循环。熟练实现位运算与辅助函数并处理边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如 n19n19 输出truen2n2 输出 false )。本文将从问题转化、平方和计算、循环检测哈希表 vs 快慢指针到代码实现层层递进。即使你对环形链表检测还不熟悉我们也会从“这个计算过程就像走一条链要么到1要么绕圈”这一直觉出发让你轻松抓住核心思想——快慢指针能判断是否有环而且空间更省。现在让我们一起在数字的平方和变换中找出那个快乐数的密码吧 ✨一.题目202. 快乐数 - 力扣LeetCode 欢迎来到「移动零」题解之旅本文将带你从“将所有零移到数组末尾同时保持非零元素顺序”这一数组操作问题出发深入理解双指针快慢指针的经典应用并掌握如何原地修改数组实现高效的一次遍历。在开始之前建议你先了解题目背景这是 LeetCode 283 题给定一个数组nums要求将所有0移动到数组末尾并保持非零元素的相对顺序不变且必须原地操作不能复制新数组。这是数组操作中的基础题也是双指针思想的入门经典。明确学习目标掌握双指针解法——维护一个“慢指针”指向已处理好的非零序列的末尾用“快指针”遍历数组遇到非零元素则交换或覆盖到慢指针位置最后将剩余位置填零。理解为什么这种“只关心非零元素遇到零就跳过”的策略能保持相对顺序并熟练处理边界如全零数组或全非零数组。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [0,1,0,3,12]输出[1,3,12,0,0]。本文将从问题转化、双指针策略设计快慢指针详解、代码模拟到复杂度分析层层递进。即使你对双指针还不熟悉我们也会从“用慢指针记录非零元素应该放的位置”这一直觉出发让你轻松抓住核心思想——快指针负责探路慢指针负责记录所有非零元素依次往前靠零自然被挤到后面。现在让我们一起把零“搬运”到末尾让数组焕然一新吧 二.做题思路一、问题分析前置分析给定正整数n不断将其替换为各位数字的平方和重复此过程。若最终能变成1则为快乐数否则会进入不含 1 的无限循环。核心观察平方和序列要么收敛到 1要么进入循环。因此检测循环是解决问题的关键。二、算法策略快慢指针使用Floyd 判圈算法快慢指针检测序列中的循环慢指针slow每次走一步计算一次平方和快指针fast每次走两步计算两次平方和。初始化slow nfast square(n)。循环直到slow fast说明检测到环。若相遇时fast 1则循环是1 - 1 - ...返回true否则进入其他循环返回false。三、正确性说明简单版本快乐数过程中的平方和序列要么最终到达 1要么会进入一个不包含 1 的循环因为数值范围有限必然重复。快慢指针能在不记录历史的情况下检测环的存在。当快慢指针相遇时若相遇点值为 1则说明序列中出现了1的循环即原数是快乐数否则说明进入了其他循环不是快乐数。该算法可检测所有情况正确性由判圈算法保证。四、实现细节边界防护辅助函数square(int n)负责计算各位数字的平方和注意循环取模直到n变为 0。初始化slow nfast square(n)快指针先走一步防止初始相等误判。循环条件为slow ! fast每次循环slow square(slow)fast square(fast); fast square(fast);快指针走两步。退出循环后判断fast 1或slow 1均可。时间复杂度O(循环步数)空间复杂度 O(1)。五、返回值目标映射返回true表示n是快乐数否则返回false。三.代码class Solution { public: // 辅助函数计算一个数各位数字的平方和 int square(int n) { int sum 0; // 累计平方和 int t 0; // 临时变量存储当前位的数字 // 循环取出 n 的每一位数字 while (n 0) { t n % 10; // 取出最低位 sum t * t; // 累加该位的平方 n n / 10; // 去掉最低位 } return sum; } bool isHappy(int n) { // 算法思路快乐数的计算过程本质上是对数值进行迭代f(n) 各位平方和 // 这个过程要么最终到达1快乐数要么进入一个不包含1的循环。 // 使用快慢指针Floyd判圈算法检测循环 // - slow 每次走一步调用一次 square // - fast 每次走两步调用两次 square // 如果它们相遇说明存在循环如果相遇时值为1则说明是快乐数。 int slow n; // 慢指针初始指向 n int fast square(n); // 快指针初始指向 f(n) // 循环直到快慢指针相遇即检测到循环 while (slow ! fast) { slow square(slow); // 慢指针走一步 // 快指针走两步连续调用两次 square fast square(fast); fast square(fast); } // 相遇时如果 fast或 slow等于1说明循环为1 - 1 - ...是快乐数 // 否则进入了其他循环如4 - 16 - 37 - ...不是快乐数。 if (fast 1) { return true; } else { return false; } } };四、流程图 闭幕 恭喜你完成了「快乐数」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用快慢指针Floyd判圈算法检测循环slow每次走一步调用一次squarefast每次走两步调用两次square。请问为什么快慢指针一定能相遇如果数字序列不存在循环会怎样辅助函数square计算各位数字的平方和这个过程是否一定会在有限步内进入循环你能从数学上解释原因吗提示数字位数与平方和的关系初始时slow nfast square(n)为什么不让两者都从n开始如果都从n开始while 循环还能正确工作吗延伸挑战如果将规则改为各位数字的立方和而不是平方和判断一个数是否为“快乐数”的算法框架是否需要改变只修改square函数是否足够如果要求输出循环中的全部数字例如当不是快乐数时输出进入循环的所有数如何基于当前代码做最小改动来实现如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案快慢指针一定能相遇因为平方和迭代在有限状态整数范围 1~2^31-1上必然出现重复一旦重复就形成环快指针终会追上慢指针这是 Floyd 判圈算法的核心。若不存在循环只有到达 1 后永远停留在 1即 1→1 的循环快慢指针依然会相遇于 1。平方和迭代必定进入循环因为对于任意n其各位平方和最大不超过9^2 * 位数当位数较多时例如 10 位数平方和最大为 810而后续值被限制在 1~810 的有限范围内因此最多迭代 810 次后必有重复进入循环。初始设置slow nfast square(n)是为了让快指针先走一步否则 while 循环一开始slow fast会直接退出无法判断循环。如果都从n开始则需要改用do-while结构。延伸挑战答案挑战1算法框架完全不变只需将square函数中的平方改为立方t*t*t即可因为底层逻辑仍然是迭代函数求值 判圈快乐数的定义仅改变平方和的函数形式判圈逻辑通用。挑战2可在快慢指针相遇后用哈希集合记录从n开始到相遇的所有数字然后从相遇点继续走记录直到回到起点即可得到完整循环序列或者修改为哈希集合方案在迭代过程中记录所有出现过的数字当发现重复且不为 1 时直接输出该循环段。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
