双指针_移动零和_复写零_c++

283. 移动零 - 力扣（LeetCode）

算法原理：

两个指针的作用：

cur ： 从左往右扫描数组，遍历数组

dest ：已处理的区间内，非零元素的最后一个位置

三个区间：

[0,dest]    [dest +1 , cur-1]  [cur, n-1]

   |                        |                   |

非零                  零              待处理

当cur为零的时候 ++cur

当cur非零的时候，cur与交换dest+1的位置进行交换

代码实现：

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

1089. 复写零 - 力扣（LeetCode）

算法原理：

1. 先找到最后一个“复写”的数

双指针算法

a，先判断cur位置的值

b，根据cur决定dest向后移动一步或者两步

c，判断一下dest是否已经到结束了

d，cur++

2.处理下边界情况

用上面的操作，这个dest的会越界

本意是将n-1的位置和n的位置置为0，但是n的位置已经越界所以只能n-1的位置为零 然后再让dest向前移动两步，cur向前移动一步即可

3.从后往前完成复写操作

代码实现

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-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--;
            }
        }
    }
};

原文地址：https://blog.csdn.net/weixin_49323800/article/details/143693936

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！