【算法挨揍日记】day01——双指针算法_移动零、复写零-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法挨揍日记】day01——双指针算法_移动零、复写零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

283.移动零

283. 移动零https://leetcode.cn/problems/move-zeroes/

题目：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

【算法挨揍日记】day01——双指针算法_移动零、复写零,算法挨揍日记,Leetcode,算法,职场和发展

解题思路：

我们可以利用两个指针（dest和cur）的方法，将这个数组分为三个区域

我们可以将dest初始化为-1，cur初始化为0

cur走一遍数组遇到的两种情况：

cur位置为0

cur位置为非0

当cur位置为0，cur++；

当cur不为0时，swap交换一下就好，dest++；

解题代码：

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

1089. 复写零

1089. 复写零https://leetcode.cn/problems/duplicate-zeros/

题目：

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

解题思路：

本题要求我们要就地修改，不能使用额外的数组，我们先用额外的数组想一想

我们发现结果是这样的

我们再将使用额外数组的双指针方法用在本地去实验一下，我们发现dest=-1和cur=0，去正向解决问题不可以，会有元素被覆盖丢失的问题！

我们试着反向去操作呢，dest=size-1（指向最后一个元素），那我们如何确定cur的位置呢？

我们可以再利用一次双指针的方法来确认cur的位置，一开始cur=0，dest=-1

遍历数组，当cur遇到0时，dest+=2；当cur遇到非0时，cur++；

这里会有一种边界情况需要我们去考虑：

示例：1 0 2 3 0

我们通过上述方式来确定cur时，会出现以下这种情况：

会出现dest越界的情况，我们考科一让size-1的位置置为0，然后cur--，dest-=2这样就可以解决问题了

然后从后向前遇到0就是置两次0，遇到非0就是复制咯，这一步简单

解题代码：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int dest=-1;
        int cur=0;
        int size=arr.size();
        //确认cur的位置
        while(cur<size)
        {
            if(arr[cur]==0)dest+=2;
            else dest++;

            if(dest>=size-1)break;
            cur++;
        }
        //边界情况，示例：1 0 2 3 0,当dest的位置越界了
        if(dest==size)
        {
            arr[size-1]=0;
            dest-=2;
            cur--;
        }
        while(cur>=0)
        {
            if(arr[cur]!=0)
            {
                arr[dest--]=arr[cur--];
            }
            else 
            {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
    }
};

【算法挨揍日记】day01——双指针算法_移动零、复写零,算法挨揍日记,Leetcode,算法,职场和发展