C/C++精品算法——双指针（1） - 实践

文章目录

• 一、前言
• 二、双指针的定义
• 三、手撕算法题
• • 3.1 移动零
  • 3.2 复写零
  • 3.3 快乐树
  • 3.4 盛最多水的容器
• 四、总结

一、前言

编程如同球场，唯有自己不断突破，才能取得最后的胜利
鑫-萍的个人主页
鑫-萍的Gittee仓库
人生名言——与其被动迎敌，不如主动出击

Hello，各位热爱编程的小伙伴们！今天的你们是否充实呢？鲁迅曾今说过——必须如蜜蜂一样，采过许多花，这才能酿出蜜来。在生活中，我们又何尝不是这样呢，唯有努力向前，才能不负韶华。好啦，划归主题，今天我要跟大家分享的内容是：C/C++精品算法——双指针。

二、双指针的定义

大家听到双指针这个名词的时候，可能大脑一片空白，双指针又是什么？从来没有听说过啊？这里，就由up来给大家进行讲解。

双指针算法是 C/C++ 中一种高效的线性 / 近线性时间复杂度算法思想，核心是通过维护两个指针（索引 / 迭代器），在遍历数据结构（如数组、链表、字符串）时协同移动，替代传统的嵌套循环，从而将时间复杂度从 O (n²) 优化到 O (n) 或 O (nlog n)，同时保持空间复杂度为 O (1)

想必大家在看完双指针的定义，在结合之前C语言和数据结构的知识，大差不差都能理解到大致的意思了吧？不过老话说得好，光看不练假把式，下面呢我给大家分享几道优质算法题，来帮助大家进一步理解双指针。

三、手撕算法题

3.1 移动零

移动零力扣链接

第一题，就先给大家一道相对简单的算法题，怎么样，在扫视完此题之后，你是否有了解题思路了呢？没有的话也没关系，请仔细观看up的解题思路再加以理解。
画图展示：

具体思路：

先定义两个变量，cur和des，让cur指向数组的第一个元素，des指向数组第一个元素的前一个元素。如果cur指向的元素为0，就让cur++指向下一个元素，如果cur指向的元素非0，就先让des++指向下一个元素，再交换cur和des所指向的元素，以此循环，直到cur超出整个数组元素个数时跳出循环。

代码展示：

class Solution {
public:
void moveZeroes(vector<int>& nums) {int cur = 0,des = -1;int n = nums.size();while(cur<n){if(!nums[cur]) cur++;//为0，cur++else swap(nums[cur++],nums[++des]);//非0，先让des++，再交换cur和des所指向的元素，再让cur++//     if(nums[cur]) swap(nums[cur],nums[++des]);//    cur++;}}};

3.2 复写零

怎么样，第一道题可谓是小试牛刀，先让大家熟悉熟悉，现在再让我们来看第二题。

复写零力扣链接

大家这时可以先暂停一下，整理整理自己的思路，再实现一下代码，稍微多花一些时间去解决这道题，如果确实做不出来，再来返回看up的解题思路。
画图展示：

具体思路：

先定义两个变量cur和des，让cur指向数组的第一个元素，让des指向数组第一个元素的前一个元素。
第一步：当cur所指向元素没有超出数组个数时，如果cur指向元素非0，就让des++走一步，如果cur指向的元素为0，就让des+=2走两步，如果des>=n-1就结束循环。
第二步：若此时des=n-1，cur所指向的元素就是要复写的最后一个元素；若此时des=n，让arr[n-1]=0，然后让cur–后退一步，des-=2后退两步，现在cur指向的元素就是要复写的最后一个元素。
第三步：从后往前复写，如果cur所指向元素非0，就交换cur和des所指向的元素，再让cur–和des–；如果cur所指向元素为0，就让des所指向的元素为0，让des–,然后再让des所指向的元素为0，再让cur–，des–。重复以上步骤，直到不满足cur>0这个循环条件时跳出循环。

代码展示：

class Solution {
public:
void duplicateZeros(vector<int>& arr) {int cur = 0,des = -1;int n = arr.size();while(cur<n)//找到也复写的最后一个元素{if(arr[cur]) des++;else des+=2;if(des>=n-1) break;cur++;}while(des==n)//判断临界情况{arr[n-1] = 0;cur--;des-=2;}while(cur>0)//从后往前进行复写{if(arr[cur]) swap(arr[cur--],arr[des--]);else{arr[des--] = 0;arr[des]=0;des--;cur--;}}}};

怎么样？这第二题你是否独立做对了呢？不知道大家有这样的一种感觉没有，这第二题明显比第一题难了不少，不过即使你没有独立的做出来也不要灰心，因为此题确实不简单哦。让我们整装待发，再来看第三题。

3.3 快乐树

快乐数力扣链接

画图展示：

具体思路：

定义快慢指针——slow和fast，slow每次走一步，fast每次走两步，若slow和fast可以相遇且都为1时，证明此数为快乐数。

代码展示：

class Solution {
public:
int Addition(int n)//求各位数的平方和
{
int ret = 0;
int tmp = 0;
while(n)
{
tmp = n % 10;
ret+=pow(tmp,2);
n = n / 10;
}
return ret;
}
bool isHappy(int n) {
int slow = n,fast = n;//定义快慢指针
while(1)
{
slow = Addition(slow);//slow每次走一步
fast =Addition( Addition(fast));//fast每次走两步
if(slow==fast)
{
return slow==1;//相等且都为1，符合快乐数定义
}
}
//下面注释为解法二
// int slow = n,fast = Addition(n);
// while(slow!=fast)
// {
//      slow = Addition(slow);
//      fast =Addition( Addition(fast));
// }
// return slow == 1;
}
};

3.4 盛最多水的容器

盛最多水的容器力扣链接

画图展示：

由上图可知，能围成的最大容积即为30

具体思路：

定义两个变量left与right，让left指向数组的第一个元素，right指向数组的最后一个元素，算出能围成的容积，然后让小的那个变量进行移动，若两个变量所指向的数值的相等，就让任意一个变量移动，按照以上进行循环，直到不满足left<right这个循环条件时，跳出循环，最后找出最大的容积即可。

代码展示：

class Solution {
public:
int maxArea(vector<int>& height) {int n = height.size();int left = 0, right = n - 1;int area = 0;while (left < right)//进入循环{if (height[left] < height[right])//左小{area = max(area, (right - left) * height[left]);left++;}else if (height[left] > height[right])//右小{area = max(area, (right - left) * height[right]);right--;}else {//相等area = max(area, (right - left) * height[right]);if (height[left + 1] < height[right - 1])  left++;else right--;// if (height[left + 1] > height[right - 1])  right--;// else left++;}}return area;}};

四、总结

怎么样，经过这四题的锤炼，你是否已经对双指针算法一定程度上地掌握了呢？总的来说，这四题相对比较简单，所以大家还是要独立地去思考和解题。学习算法的道路上，总是充满坎坷，但是只要我们努力，这些算法题总会被我们理解透彻，可谓是——刷题百遍，其意自现。