简单的英文网站模板,湘潭做网站 都来磐石网络,哈尔滨建站多少钱,wordpress链接数据库间歇出错前言
本篇博客为大家介绍双指针问题#xff0c;它属于优选算法中的一种#xff0c;也是一种很经典的算法#xff1b;算法部分的学习对我们来说至关重要#xff0c;它可以让我们积累解题思路#xff0c;同时也可以大大提升我们的编程能力#xff0c;本文主要是通过一些题…前言
本篇博客为大家介绍双指针问题它属于优选算法中的一种也是一种很经典的算法算法部分的学习对我们来说至关重要它可以让我们积累解题思路同时也可以大大提升我们的编程能力本文主要是通过一些题目来为大家介绍这里统一说明一下每一道题我会粘贴原题链接大家可以先做再来看解析这样会更有针对性下面进入正文。
1. 移动零
题目链接. - 力扣LeetCode 题目解析本题大家读完后应该可以很轻松地理解题目的意思我们需要将0全部移动到数组的末尾并且保持其他元素的顺序是不能改变的。
算法原理这类题可以划归为数组分块问题对于这类问题首先想到的方法就是双指针大家注意这里提到的指针并不是我们在C语言中学过的那个指针这里的“指针”代表数组的下标。我们需要定义两个“指针”一个指针用于遍历数组另一个指针用来存储非零元素的最后一个位置这两个“指针”会将整个数组划分为3个区间。
具体大家来看下图
区间划分完后我们需要让两个“指针”移动的过程中保持它们本身的性质这样我们就可以解决这个问题那么我们该如何保持呢 大家可以结合题目给的例子来进行理解上面的思路就是双指针的核心思路。
代码实现
class Solution {
public:void moveZeroes(vectorint nums) {int cur0;int dest-1;for(cur0;curnums.size();cur){if(nums[cur]){swap(nums[dest],nums[cur]);}}}
};
这里使用C实现代码一个for循环就搞定了主要就是在于指针的调整。
2. 复写零
题目链接. - 力扣LeetCode 题目解析本题要求我们来对0进行复写其实就是遇到0了抄两遍不是0就抄一遍注意题目要求就地修改不能开辟新的数组。
算法原理首先我们需要定义两个指针其次需要找到最后一个复写的数最后从后向前进行复写操作具体大家请看下图 这里大家要注意我们在找最后一个复写的数的时候也同样需要用到双指针算法其中有越界的情况我们要进行特殊处理。
代码实现
class Solution {
public:void duplicateZeros(vectorint arr){//第一步找最后一个复写的数int cur0;int dest-1;int narr.size();while(destn){if(arr[cur]){dest;}else{dest2;}if(destn-1){break;}cur;}//第二步处理边界if(destn){arr[n-1]0;cur--;dest-2;}//第三步从后向前复写while(cur0){if(arr[cur]){arr[dest--]arr[cur--];}else{arr[dest--]0;arr[dest--]0;cur--;}}}
};
这里大家看到代码分为三部分找最后一个复写的数、处理边界以及复写操作还有一个小问题有同学会想为什么必须从后往前进行复写不能从前往后吗
答案是不可以大家思考一下如果从前往后复写那么0要写2遍这个时候我们原始的数据就会被覆盖这样就无法达到题目的要求。
3. 快乐数
题目链接. - 力扣LeetCode 题目解析本题要求我们判断一个数是否为快乐数那么我们首先要明确什么是快乐数然后我们进行判断是快乐数返回1否则返回0。
算法原理这道题我们也可以使用双指针来解决具体来说就是快慢指针大家可以先回想一下我们在链表的学习中遇到的这么一道题题目要求我们判断环形链表当时我们使用了快慢指针的方法来解决那么本题我们同样可以使用这种思想来解决。根据之前的结论大家首先需要明确当我们不断进行题目要求的操作时一定会进入一个循环这里要么是1一直循环要么是循环其他不为1的数据所以每次计算得到的数可以串起来看成一个“链表”这样就和我们之前说过的环形链表殊途同归了。我们只需要定义一个慢指针一个快指针在循环的过程中快指针一定会追上慢指针我们判断相遇的时候的值是不是1即可判断给定的数是不是快乐数。 代码实现
class Solution
{
public:int test(int n){int sum0;while(n){int tn%10;sumt*t;n/10;}return sum;}bool isHappy(int n) {int slown;int fasttest(n);while(slow!fast){slowtest(slow);fasttest(test(fast));}return slow1;}
};
这里补充一个小问题就是实现题目中要求的操作每一位的平方和相加这个想必大家在C语言阶段就已经接触过这里大家看代码应该很容易理解。
4. 盛水最多的容器
题目链接. - 力扣LeetCode 题目解析本题要求找到盛水最多的容器本质就是让我们找出两个数来确定一个容器使这个容器的“容积”最大那么本题大部分人的第一反应就是暴力枚举把每一个乘积都求出来然后对比找出最大的这是一种很容易理解的思路但是代码的时间复杂度会非常高效率就比较低所以不可行。
算法原理本题我们要使用双指针来解决问题具体是运用左右指针一个指针从左往右另一个指针从右往左两个指针向中间靠拢哪边高度小哪边就往里动下面说明了这样做的原理利用了单调性来找到规律。 代码实现
class Solution {
public:int maxArea(vectorint height) {int left0;int rightheight.size()-1;int ret0;while(leftright){int vmin(height[left],height[right])*(right-left);retmax(ret,v);if(height[left]height[right]){left;}else{right--;}}return ret;}
};
5. 有效三角形的个数
题目链接. - 力扣LeetCode 题目解析本题要求我们在一组数中选出可以构成三角型的数字组合其实就是求有多少种选法这里大家注意看例子的提示重复选的数也是OK的只要是不同位置的数就满足条件。
算法原理
本题我们不能使用暴力解法来做那样时间复杂度太高效率很低那么我们进行优化使用双指针来解决问题具体流程大家可以看下图首先我们先将数据进行排序再来固定最大的数然后定义左右两个指针根据两种不同的情况移动指针循环操作就可以解决本题。 代码实现
class Solution {
public:int triangleNumber(vectorint nums) {//排序sort(nums.begin(),nums.end());int ret0;int nnums.size();for(int in-1;i2;i--)//固定最大数{int left0;int righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}return ret;}
};
6. 查找总价格为目标值的两个商品
题目链接. - 力扣LeetCode 题目解析本题的要求很简单就是让我们在一组数中找到两个数使它们的和等于目标值。
算法原理本题其实大部分人第一时间还是会想到暴力解法运用了两个循环遍历所有情况判断是否等于target这样做很好理解但是代码的时间复杂度会很高会超时所以这种暴力解法不建议。优化版的解法就是使用双指针定义左右指针分为三种情况来决定指针的移动具体大家请看下图。 代码实现
class Solution {
public:vectorint twoSum(vectorint price, int target) {int nprice.size();int left0;int rightn-1;while(leftright){if(price[left]price[right]target){left;}if(price[left]price[right]target){right--;}if(price[left]price[right]target)return {price[left],price[right]};}return {-1,-1};}};
总结
本篇博客为大家介绍了双指针算法它可以帮助我们解决很多原本复杂的问题大家需要掌握这种思想当我们遇到需要将数据分区间进行处理的时候我们可以考虑双指针这其中还包括了快慢指针的思路最后希望本篇博客可以为大家带来帮助感谢阅读
