目录 移动零283题目要求核心思路代码实现探索思考 复写零1089题目要求核心思路代码实现探索思考 快乐数202题目要求核心思路代码实现探索思考 刷题总结最近刷了三道经典的算法题分别是「移动零」「复写零」和「快乐数」每一道都有巧妙的解题思路。我想把这些思路和对应的代码实现记录下来也算是一次探索性学习的总结。 移动零283题目要求把数组里所有的0移动到末尾同时保持非零元素的相对顺序必须原地操作。核心思路这是一个典型的双指针问题left指针指向当前可以放置非零元素的位置初始为-1right指针遍历整个数组当right遇到非零元素时就和left1位置的元素交换这样保证了非零元素的顺序也把0挤到了后面代码实现class Solution { public: void moveZeroes(vectorint nums) { int left -1, right 0; while (right nums.size()) { if (nums[right] 0) { right; } else { swap(nums[left], nums[right]); } } } };探索思考这道题的关键是理解 “原地操作” 的含义。如果允许使用额外数组直接把非零元素存进去再补零就可以了但双指针的方法让空间复杂度降到了O(1)是最优解。 复写零1089题目要求遍历数组遇到0就把它复写一遍后面的元素右移且不能超过数组长度。核心思路这道题的难点在于如果直接从前往后复写会覆盖掉还没处理的元素。所以我们用两次遍历的思路第一次遍历用cur和dest两个指针计算出最终每个元素的目标位置找到最后一个需要保留的元素。第二次遍历从后往前复写这样就不会覆盖未处理的元素。如果最后一个元素是0且刚好超出数组长度需要单独处理。代码实现class Solution { public: void duplicateZeros(vectorint arr) { int cur 0, dest -1; int n arr.size(); // 第一次遍历找到最终的位置 while (cur n) { if (arr[cur]) dest; else dest 2; if (dest n - 1) break; cur; } // 处理边界情况最后一个0复写后超出数组 if (dest n) { arr[n - 1] 0; cur--; dest - 2; } // 第二次遍历从后往前复写 while (cur 0) { if (arr[cur]) { arr[dest--] arr[cur--]; } else { arr[dest--] 0; arr[dest--] 0; cur--; } } } };探索思考从后往前的逆向思维是这道题的精髓。如果正向操作每次遇到0都要移动后面的元素时间复杂度会达到O(n²)而两次遍历的方法把时间复杂度降到了O(n)非常高效。 快乐数202题目要求判断一个数是不是快乐数反复计算各位数字的平方和最终如果能得到1就是快乐数否则会进入无限循环。核心思路这道题的关键是如何判断 “无限循环”。我们可以用 ** 快慢指针Floyd 判圈算法** 来检测循环slow指针每次计算一次平方和fast指针每次计算两次平方和如果存在循环fast最终会追上slow如果是快乐数slow会先到达1代码实现class Solution { public: int bitsum(int n) { int sum 0; while (n) { sum pow(n % 10, 2); n n / 10; } return sum; } bool isHappy(int n) { int slow n, fast bitsum(n); while (slow ! fast) { slow bitsum(slow); fast bitsum(bitsum(fast)); } return slow 1; } };探索思考这道题也可以用哈希表来记录已经出现过的数字但快慢指针的方法不需要额外空间空间复杂度是O(1)。而且判圈算法在很多链表问题中也会用到是一个非常通用的技巧。 刷题总结这三道题虽然看起来不同但都用到了双指针的核心思想移动零同向双指针一个负责找非零元素一个负责放置复写零两次遍历正向找位置逆向写元素快乐数快慢指针检测循环探索性学习的乐趣就在于你会发现很多看似无关的问题背后都有相通的解题思路。多总结、多思考才能真正把算法内化成自己的能力。