移动零+复写零+快乐数+盛最多水的容器+有效三角形的个数

前言

2025.3.31，今天开始每日五道算法题，今天的算法题如标题！

双指针算法

在做今天的算法题之前，先来介绍一下今天会用到的算法！

双指针算法分为了两种常见的形式：对撞指针和快慢指针！

对撞指针，顾名思义就是会碰撞到一起去，那么这两个指针就会形成一左一右向中间移动！

一般来说，对撞指针的结束条件有两种：

        两个指针在同一个位置！即 left == right；

        两个指针交错！即 left > right；

快慢指针，也叫龟兔赛跑算法，基本思想为两个不同速度的指针在数组或链表等序列结构上移动。

我们常见的就是环状结构就会用到我们的快慢指针！

那么介绍完今天的算法，那么就直接到我们的题目当中吧！

移动零

传送门如下：

283. 移动零 - 力扣（LeetCode）

先来看一下题目

题目解析

我们先来看一下结果，我们可以看到明显分为了两个区块，左区块都是非0的数，右区块都是0的数。那么我们就定义[0,slow]为非0的区块，[slow+1,num.size()-1]为0的区块。

可以看到！只需要保持两个指针分割这两个区间即可！也就是[0,slow]和[slow+1,fast-1]，至于[fast,num.size()-1]这个待处理区间，我们暂时不考虑。

---

那么我们就可以定义两个指针的作用

fast指针：用于遍历整个数组。

slow指针：用于分割非0和0区块，指向的是最后一个非0元素！

---

那么我们来考虑fast指针和slow指针初始化的值！

由于我们是不知道一开始非0元素是在哪个位置，所以我们将slow指针设置为-1，由于我们的fast指针是用于遍历整个数组的，所以我们设置为0即可！

---

那么我们继续来考虑两个指针移动的规则！

我们以fast指针作为参考！也就是两种情况！

1.遇到的元素为0，我们只需要将fast指针继续++即可。

        因为我们的目标是[slow+1,fast-1]的区间为0区块,我们的slow是不需要往前走的，fast向前走一步是能够包裹住这个遇到的元素为0的块的！

2.遇到的元素为非0，我们就需要将fast当前位置的元素和slow当前位置+1的元素进行互换，并且两个指针都++

        因为[slow+1,fast-1]都是0，遇到的fast为非0，互换之后slow+1就是非0，fast就是0，那么两个指针++之后，也是符合[slow+1,fast-1]为0区间，而且[0,slow]为非0区间。

---

那么这里我们就把情况考虑完成！那么我们什么时候停止移动？

当然是我们的fast指针到了我们数组的尾部啦！

那么我们再来考虑一个特殊情况！

当我们的数组只有一个元素，非0或0是否满足以上我们分析的过程？

1.当这个元素是0，我们fast直接跑出去了，就不需要循环了。满足！

2.当这个元素不是0，我们的fast也就是0号位元素和slow+1也就是0号位元素进行交换。满足！

---

代码编写

所以理论成立！我们直接开始代码的编写！

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int fast = 0, slow = -1; fast < nums.size(); fast++){if(nums[fast]){swap(nums[++slow], nums[fast]);}}}
};

提交我们的结果！

那么这一题我们就完成啦！

复写零

传送门如下：

1089. 复写零 - 力扣（LeetCode）

先来看一下题目！

题目解析

我们看到这个题，需要进行原地修改，所以我们不可能去考虑从左到右去进行复写！

为什么呢？因为我们复写的时候会覆盖掉我们后面的元素。所以我们就要从右往左进行覆写！这样我们就不会覆盖掉前面的元素！

---

之后我们发现，我们只知道要覆盖最后一个元素开始，但是不知道是哪个元素覆盖过来，所以我们就要先找到第一个要覆写的元素。

---

那么我们就需要使用到快慢指针去找到我们的第一个要覆写操作的元素！

我们先考虑边界情况，因为我们后续找到了第一个要覆写的元素的位置，我们的快指针也会达到边界的位置，我们移动两步的这个操作很有可能会越界，所以我们需要考虑边界问题！毕竟我们要重复利用这两个指针的嘛！

这里也不是很难哦，只需要考虑我们的快指针刚好等于数组大小即可！

我们只需要将整个数组的最后一个元素设置为0，之后我们的快指针-2，慢指针-1即可。

为什么呢？如果我们会越界，那么只有一种情况，就是我们遇到了0，我们移动了两次，那么数组只剩一个位置了，那么这个位置只能是0，我们就需要设置最后一个位置为0，而且快指针移动了两次，我们就在数组最后的那个位置的后一位，由于我们不需要操作最后一位，所以我们就需要回退两位，到数组的最后一位进行操作，那么最后一位已经操作，那么我们的慢指针现在所在位置就是已经操作过的位置，那么我们的慢指针也需要回退一位。

---

那么考虑了我们的边界问题，我们就来考虑找第一个需要覆写的位置。

我们要考虑的就是快慢指针进行移动的规则！

1.慢指针遇到非0元素，我们两个指针都移动一个单位即可

2.慢指针遇到0元素，我们的慢指针移动一位，快指针移动两位即可！

---

那么考虑完找到第一个覆写位置，我们就要考虑怎么样覆写

1.slow指针位置元素为0，fast-1和fast位置都改为0，slow-=1，fast-=2

2.slow指针位置元素为非0，fast位置改为slow指针位置元素，slow-=1，fast-=1

---

代码编写

理论成立，我们赶快进行代码的编写！

class Solution  {
public:void duplicateZeros(vector<int>& arr) {int fast = -1,slow = 0;int sz = arr.size();// 1. 先找到最后一个数while(fast < sz){if(arr[slow])fast++;elsefast += 2;if(fast >= sz-1)break;slow++;}// 2. 处理边界情况if(fast == sz){arr[sz-1] = 0;fast -= 2;slow--;}// 3. 从后向前完成复写while(slow >= 0){if(arr[slow])arr[fast--] = arr[slow--];else{arr[fast--] = 0;arr[fast--] = 0;slow--;}}}
};

看一下提交结果

快乐数

传送门如下：

202. 快乐数 - 力扣（LeetCode）

我们还是先来看一下题目

题目解析

我们一眼就看到了这个无限循环这四个字，说明什么？

我们要用快慢指针去找循环圈子！快指针移动两步，慢指针移动一步，当两个指针重合时候就可以说明我们的这个数是否为快乐数！其实就是判断链表是否有环的题！

但是，我们发现，其实一堆1其实也是可以组成一个为1的环，只不过是在自己身上转而已。

所以我们考虑的就是当这个快慢指针的值重合的时候是否为1即可！

这里我们其实就已经把题目做出来了，那么直接就到我们的代码编写！

代码编写

class Solution {
public:int bitSum(int num){int sum = 0;while(num){int b = num % 10;sum+= b*b;num = num / 10;}return sum;}bool isHappy(int n) {int slow = n;int fast = bitSum(n);while(slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}if(slow == 1) return true;return false;}
};

看一下提交结果！

盛最多水的容器

传送门如下：

11. 盛最多水的容器 - 力扣（LeetCode）

先来看一下题目

题目解析

我们这道题其实就是计算体积，木桶效应，最短的那个作为高，这个体积就是长*高

当然这道题我们不打算使用暴力枚举！所以我们就要用对撞指针来使得整个计算体积的长最大！

我们举个例子来模拟一下！

[1,8,6,2,5,4,8,3,7]

我们可以看到数组的0号位和数组的8号位也就是最后一位！此时体积为（8-0）* 1 = 8

如果我们使用1和3进行计算，高度肯定不变，但是长减少了，所以我们就不需要考虑了，我们就直接开始考虑左边的8和7进行考虑。

同理应该去掉3，所以我们只需要对撞指针选择最大的元素留下，最小的元素剔除，之后计算出当前最大的体积即可！之后比较当前最大体积就可以算出最大体积了！

---

那么为什么我们要剔除较小的元素？

因为我们剔除一个元素，宽度一定会减少，但是我们要尽可能让高度变大！

---

那么还有一个问题，遇到两个相同大小的元素时应该如何抉择？

其实都一样！你就算移动那个旁边是一个很大的数的指针，这高度还是原来的那个元素，但是我们的宽度还是减小的，所以相同大小的元素不需要考虑特殊情况，只需要按照你的习惯去移动就行。

代码编写

那么直接到代码编写！

class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size()-1;int ret = 0;while(left < right){int v = min(height[left], height[right]) * (right - left);ret = max(ret, v);if(height[left] < height[right]){left++;}else{right--;}}return ret;}
};

来看一下结果！

有效三角形的个数

传送门：

611. 有效三角形的个数 - 力扣（LeetCode）

我们先来看一下题目

题目解析

首先不是侮辱大家！我们先来看一下是否为三角形的定理！

a + b > c

a + c > b

b + c > a

这个看起来就很乱，需要证明三个条件，但是如果我们知道a <= b <= c，就只需要证明一个条件即可！毕竟c大于等于任何一条边

所以这道题我们就需要先排序！

---

那么排完序，我们来举个例子！

假如有一个数组为[1, 2, 2, 3,5,9,11]

我们先固定最大值11

我们再用碰撞指针！找到了1和9小于11，由于单调性，只能移动我们的左指针，找到了3，可以看到3 + 9 > 11,那么继续移动左指针还会变大，所以能够组成三角形的就只有[3,9,11]和[5,9,11]两组，其实就是9的数组坐标-3的数组坐标，也就是右指针-右指针的值。此时就可以移动右指针了，3 + 5 < 11，左指针右移，碰撞了，所以就结束了这一轮，那么就完成了和固定值11的三角形边配对了。

那么固定值9同理。

---

总结规律：

已知 a <= b <=c

        a + b > c   得   ret = right - left 且 right--

        a + b <= c 得   left++

---

代码编写

理论成立，代码编写！

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int sz = nums.size();int ret = 0;//遍历固定最大值for(int i = sz -1; i>=2; i--){int left = 0;int right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
};

我们来看一眼运行结果

那么今天的五道算法题就到此为止，我们期待下一期！