个人主页 : zxctscl
如有转载请先通知
1. 283. 移动零
1.1 分析
一、题目分析
要将0放在所有数组的最后,而且非零元素的顺序保持不变,要求原地对数组进行移动。
二、算法原理
用两个指针来讲数组进行划分,一个cur:从左往右扫描数组,遍历数组;一个dest:已经处理的区间内,非零元素的最后一个位置。
就将数组分为3个区间:非零:[0,dest];0区间:[dest+1,cur-1];待处理的区间:[cur,n-1].
要想这样划分,cur就得从前往后在遍历的过程中,遇到0元素,就加加;遇到非零元素,就将dest+1位置和cur位置的值交换。
1.2 代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int cur=0,dest=-1;cur<nums.size();cur++)
{
if(nums[cur])
{
swap(nums[++dest],nums[cur]);
}
}
}
};
2. 1089. 复写零
2.1 分析
一、题目解析
要求每次遇到0就复写,而且不能改变原数组的长度。
二、算法原理
如果用双指针从前往后遍历,就拿例1来说,
就会出现值被覆盖的情况:
所以遍历顺序就不能从前往后。
那么就把顺序改为从后往前遍历,但是不能超过原数组的长度,就得先找一下cur和dest开始的位置。
可以先用双指针算法:1.先判断cur位置;2.决定dest向后移动一步或者两步;3.判断一下dest是否已经到达结束位置;4.在把cur加加。
但是可能会出现dest越界的情况,如果n-1位置为0,那么cur就减减,dest就减2。
最后在从后往前开始复写0。
2.2 代码
class Solution {
public:
void duplicateZeros(vector<int>& 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++;
}
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--;
}
}
}
};
3. 202. 快乐数
3.1 分析
一、题目分析
题目中所说最后的平方和为1才是快乐数,如果不为1,就一直循环,其实可以看成两个都是循环,一个一直循环的是1,另一个循环的值都不相同。只需要判断循环里面的值是不是为1就可以。
二、算法原理
先用一个变量sum记录最后平方和,然后把最后一位平方,然后删掉原来的数,一直重复这个过程,直到最后一位为0,最后返回这个平方和sum。
定义两个快慢指针,用平方和来充当指针,slow指向第一个数,fast指向第二个数,如果这两个指针一直不相等,就一直循环,slow走一步,fast走两步。直到两个相遇为止,等于1就是快乐数,不等于就不是。
3.2 代码
class Solution {
public:
int bitsum(int n)
{
int sum=0;
while(n)
{
int t=n%10;
sum+=t*t;
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;
}
};
4. 11. 盛最多水的容器
4.1 分析
一、题目分析
题目中的数组代表每一条线的高度,来求最大的容积,来看一下例1:
选择的高度是8和7,但是题目要求不能倾斜,这里选择高度的就是7,宽度就是下标之间的差值8-1也就是7,那么容积最大就是7*7=49。
二、算法原理
用两个指针来记录容器两边的高度,可以直接先选择最大的宽度,记录下这个容积。
如果左边指针走一步,宽度在减小,高度可能会出现比之前的小,那么体积就比原来的小;高度如果不变,那么宽度减小,那么总容积也是在减小的。所以得干掉高度小的那一个值。
如果两个指针指向的值相等,那么干掉谁都可以,然后继续枚举里面相乘的容积,直到两个指针相遇,最后返回容积最大的值就行。
4.2 代码
class Solution {
public:
int maxArea(vector<int>& height) {
int left=0,right=height.size()-1,v=0;
int ret=0;
while(left<right)
{
v=min(height[left],height[right])*(right-left);
ret=max(ret,v);
if(height[left]<height[right])left++;
else right--;
}
return ret;
}
};
5. LCR 179. 查找总价格为目标值的两个商品
5.1 分析
一、题目分析
只需要找到两个数,他们的和等于目标值就可以,但是题目中的数组是按照升序排列的,暴力解法会超时,就不考虑了。
二、算法原理
利用数组是有序的,用双指针算法来算。
定义两个指针,一个在左边,一个在右边。
先计算两个指针指向值的和,判断一下和目标值的大小,会出现三种情况:1.小于目标值,那么左边指针就加加;2.等于就返回这两个值;3.大于目标值,那么右边指针就减减。
5.2 代码
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left=0,right=price.size()-1,sum=0;
while(left<right)
{
sum=price[left]+price[right];
if(sum<target)left++;
else if(sum>target)right--;
else return{price[left],price[right]};
}
return {-1,-1};
}
};
6. 15. 三数之和
6.1 分析
一、题目分析
题目要求返回三元数组和为1的三个不同的数,而且要求去重,来看一下例1:
它里面有[-1,0,1]、[0,1,-1]、[-1,2,-1],但是第一组和第二组的元素是相同的,就只能返回一个。
为了避免去重,可以先给数组排个序。
二、算法原理
排序之后,数据是有序的,这里就用双指针算法。
这里是三个数的和,可以先固定一个数a,仅想要保证这个a是小于0就行(在后面等于0相加的值不可能等于0),然后在该数后面的区间内,利用双指针算法,快速找到两个数的和,者两个数的和是a的相反数,这样这三个数相加的时候,值就为0。
这里还有可能不止一种情况,所以不要漏掉,在找到一种情况时候,左边指针和右边指针继续缩小区间找,直到两个指针相同。
那么怎么去重,已经是有序的数组,那么连续相同值的情况就不考虑了,就是在左边指针和右边指针已经找到值,就跳过重复的值。当使用完重复的元素时候,固定值也得跳过重复值。还得避免越界的情况。
文章来源:https://www.toymoban.com/news/detail-857462.html
6.2 代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
int n=nums.size();
for(int i=0;i<n;)
{
if(nums[i]>0)break;
int left=i+1,right=n-1,target=-nums[i];
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<target) left++;
else if(sum>target)right--;
else
{
ret.push_back({nums[i],nums[left],nums[right]});
left++;right--;
while(left<right&&nums[left]==nums[left-1])left++;
while(left<right&&nums[right]==nums[right+1])right--;
}
}
i++;
while(i<n&&nums[i]==nums[i-1])i++;
}
return ret;
}
};
有问题请指出,大家一起进步!!!文章来源地址https://www.toymoban.com/news/detail-857462.html
到了这里,关于【算法】双指针算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!