图网,新网站排名优化,阿里云做网站号码,wordpress修改角色管理【算法笔记】双指针算法深度剖析 #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;算法笔记 文章目录 【算法笔记】双指针算法深度剖析前言一.移动零1.1题目1.2思路分析1.3代码实现 二.复写零2.1题目2.2思路分析2.3代码实现 三.快乐数3.1题目…【算法笔记】双指针算法深度剖析 个人主页大白的编程日记
专栏算法笔记 文章目录 【算法笔记】双指针算法深度剖析前言一.移动零1.1题目1.2思路分析1.3代码实现 二.复写零2.1题目2.2思路分析2.3代码实现 三.快乐数3.1题目3.2思路分析3.3代码实现 四.盛水最多的容器4.1题目4.2思路分析4.3正确性证明4.4代码实现 五.有效三角形个数5.1题目5.2思路分析5.3代码实现 六.两数之和6.1题目6.2思路分析6.3代码实现 七.三数之和7.1题目7.2思路分析7.3代码实现 八.算法总结后言 前言 哈喽各位小伙伴大家好今天给大家分享的是入门算法双指针。算法我们程序员必备的技能。话不多说咱们进入正题向大厂冲锋 一.移动零
1.1题目
题目移动零
1.2思路分析
这里我们无非就是想让数组维持非0元素在前0元素在后的区间状态。同时不改变非0元素的相对顺序。那我们可以用区间思想借助双指针维护我们的区间状态。
1.3代码实现
class Solution {
public:void moveZeroes(vectorint nums) {for(int cur0,dest-1;curnums.size();cur)//初始化同时扫描数组{if(nums[cur])//判断是否非0{swap(nums[dest],nums[cur]);//dest移动后交换}}}
};
//分成三个区间未处理区
//处理区分区为非0元素区和0元素区二.复写零
2.1题目
题目复写零
2.2思路分析
我们从左往右无法复写因为会覆盖后面的数据。但是从右往左复写可以。所以我们找到最后一个复写的数处理一下特殊情况从右往左复写即可。
2.3代码实现
class Solution {
public:void duplicateZeros(vectorint arr) {int dest-1,cur0,narr.size();while(destn-1)//找到最后一个复写数{if(arr[cur]0){dest;}dest;if(destn-1){break;}cur;}if(destn)//防止越界{arr[--dest]0;dest--;cur--;}while(cur0)//从后往前复写{if(arr[cur]0){arr[dest--]0;arr[dest--]0;cur--;}else{arr[dest--]arr[cur--];}}}
}; 三.快乐数
3.1题目
题目 快乐数
3.2思路分析
这里我们根据鸽巢原理就可以把题目转化为判断入环点是否为1。 具体快慢指针相遇的问题可以看这篇 快慢指针相遇证明
3.3代码实现
这里我们用两个变量代替指针的作用。
class Solution {
public:int bitSum(int n)//计算每个数的平方和{int sum0;while(n){sumpow(n%10,2);n/10;}return sum;}bool isHappy(int n) {int slowbitSum(n);int fastbitSum(slow);while(slow!fast){slowbitSum(slow);fastbitSum(fast);fastbitSum(fast);}return slow1;//判断入环点是否为1}
};四.盛水最多的容器
4.1题目
题目盛水最多的容器
4.2思路分析
这里我们需要观察规律解题。
4.3正确性证明 4.4代码实现
class Solution {
public:int maxArea(vectorint height){int max0;int left0,rightheight.size()-1;while(leftright)//双指针法{int vfmin(height[left],height[right])*(right-left);//保存枚举的最大值maxfmax(v,max);//更新最大值height[left]height[right]?left:right--;}return max;}
};五.有效三角形个数
5.1题目
题目有效三角形的个数
5.2思路分析
这里我们用排序的单调性做优化. 正确性证明上一个题解有这里就不过多赘述了。
5.3代码实现
class Solution {
public:int triangleNumber(vectorint nums) {int ret0;sort(nums.begin(),nums.end());for(int inums.size()-1;i2;i--)//固定最大的数{int left0,righti-1;while(leftright){int tnums[left]nums[right];if(tnums[i])//大于{ret(right-left);right--;}else//小于{left;}}}return ret;}
};六.两数之和
6.1题目
题目两数之和 这里题目改了但是题意是一样的
6.2思路分析
这里依旧是按照单调性优化。 需要注意的是如果我们找到存在多个结果我们找到结果后让left和right指针继续移动查找即可。
6.3代码实现
class Solution {
public:vectorint twoSum(vectorint nums, int target) {sort(nums.begin(),nums.end());//排序int left0,rightnums.size()-1;while(leftright){int tmpnums[left]nums[right];if(tmptarget){left;}else if(tmptarget){right--;}else //找到结果{return {nums[left],nums[right]};}}return {};}
};七.三数之和
7.1题目
题目三数之和
7.2思路分析
这里我们可以转化为两数之和来解决问题。但是要注意去重的问题。
7.3代码实现
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;sort(nums.begin(),nums.end());for(int i0;inums.size()-2;)//固定最左边的指针{if(nums[i]0)//大于没结果{break;}int lefti1,rightnums.size()-1;int target-nums[i];//找两数之和while(leftright)//左右指针两数之和先移动再比较{int tmpnums[left]nums[right];if(tmptarget)//小于{left;while(leftrightnums[left]nums[left-1])//跳过重复元素去重{left;}}else if(tmptarget)//大于{right--;while(leftrightnums[right]nums[right1])//跳过重复元素去重{right--;}}else//相等{ret.push_back({nums[i],nums[left],nums[right]});//记录结果left;right--;while(leftrightnums[left]nums[left-1])//跳过重复元素去重{left;}while(leftrightnums[right]nums[right1])//跳过重复元素去重{right--;}}}i;while(inums.size()nums[i]nums[i-1])//跳过重复元素去重{i;}//去重}return ret;}
};八.算法总结 双指针算法总体来说就是利用两个指针根据题目要求灵活结合单调性区间思想以及题目场景用指针的移动访问解决问题。总而言之双指针需要根据题目灵活使用解决问题 后言 这就是双指针算法原理的深度剖析这些题目基本包含了双指针的所有解题方法。大家自己好好消化。感谢大家的耐心垂阅今天就分享到这咱们下期见拜拜~
