双指针刷题(一)

发布时间:2023年12月28日

所有算法文章链接(最底部)http://t.csdnimg.cn/fYYv6

1.移动0

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

分析题意

把所有的 0 都移动道数组的末尾,非 0 元素的相对顺序是不变的并且不允许创建新的数组。

例:输入:[3,0,5,7,0,8]?

? ? ? ?输出:[3,5,7,8 ,0, 0]

算法原理

这道题是一个非常经典的双指针算法,这种题的特征是把一个数组划分成若干个区间。

这道题无非就是把数组分成了两个区间,全是0元素的区间和全是非零元素的区间。

我们需要定义两个指针cur和dest

cur:从左向右扫描,遍历数组。

dest:维护非0区间,是已处理区间非零元素的最后一个位置。

三个区间

非0元素区间[0,dest]

0元素区间[dest+1,cur-1]

未处理区间[cur,n]

定义cur和dest两个变量,这里需要注意的是dest是从0开始的,当遍历数组第一个元素的时,非0元素的区间时不存在的所以dest的初始值设为-1

cur向后遍历数组,遇到0就直接跳过,遇到非0元素就放到非0元素区间里。

在cur遍历数组的过程中,要保持这三个区间的性质不变。

参考代码

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

2.复写0

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

分析题意

把数组中出现的0,全部都写一遍,将后面的元素平移,这个数组的长度是固定的,超出的元素就不写了,要求不能创建新的数组。

输入:[1,6,0,0,5,4]

输出:[1,6,0,0,0,0]

解法

首先可以先使用异地操作,再将异地操作修改为原地操作。

nums1[6] = {1,6,0,0,5,4},nums2[6]={0};

遍历nums1遇到非0元素直接尾插到nums2中,遇到0元素插入两个0元素到nums2中,直到nums2满了。

修改为异地操作

在题目里有个特别醒目的词“元素右移”,看到移动元素,那么这道题很有可能,是从后向前遍历的,因为从从前向后遍历元素,就会涉及到,覆盖的问题。

[1,0,2,3]

就像这个遍历到0,复写直接会把2给覆盖掉。

1.找到最后一个复写的数(利用双指针)

先判断cur位置的值

决定dest要向后移动一步或两步

判断dest是否到数组的末尾

cur++

2.处理边界

dest = -1 cur = 0

当测试用例为[1,0,2,3,0,4]的时候,当cur走到第二个0的时候,dest向后移动两位,造成越界。

直接把最后位置的元素置为0。

dest回退两个元素

cur回退一个元素

3.从后向前完成复写

从后向前遍历,cur遇到0,dest--两次,把两个位置改为0,遇到非0,dest--,将dest位置的元素,改为cur位置的元素。

参考代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0 ,dest = -1,n = arr.size();//利用双指针,寻找到复写的第一个元素
       while(cur < n){
           if(arr[cur])dest++;
           else dest+=2;
           if(dest>=n)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--;
            }
       }
    }
};

文章来源:https://blog.csdn.net/W2155/article/details/135263695
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。