【蓝桥杯】每天一题，理解逻辑（2/90）【LeetCode 复写零】

闲话系列：每日一题，秃头有我，Hello！！！！！,我是IF‘Maxue，欢迎大佬们来参观我写的蓝桥杯系列，我好久没有更新博客了，因为up猪我寒假用自己的劳动换了台新电脑，没用父母的钱哦！！！，虽然进度慢了，但是值得，蓝桥杯快开始了，所以我也开始努力起来了。同时，我也欢迎各位大佬互三，看到我会及时回复的！！！

放一张崩铁阿刃在这，斩除大家的霉运！！！！！
@[TOC]

题目解析

算法原理（双指针）

• 在数组中操作元素的题目，一般都用双指针算法
  • 现根据“异地”操作，再优化双指针下的“就地”操作

    • 例子

    • 

      • 定义两个指针cur和dest，分别指向两个数组的开头，当cur识别非零元素直接拷贝到dest指向的数组，遇到0元素直接写两遍，直到dest的数组元素的最大值

      • 例子优化成一个数组

        • 该题目从左到右无法进行复写，所以最好的方法是从右到左

      • 

        • 先找到最后一个“复写”的数
          1. 用双指针算法，dest定义是否为结果中的最后一个位置，cur从前到后遍历数组，
          2. 第一步 先cur先进行遍历，判断cur是否为0，
          3. 第二步 移动dest一步或两步，
          4. 第三步 判断dest是否已经结束为止。
          5. 第四步 cur++**
          6.

          • 非零元素移动一步

          • 0元素移动两步
            

          • dest结尾结束

          特例：

        • 当cur遍历过程中，遇到0元素，dest正好超出边界

        • 

          - 处理情况
          - 让cur退一步，dest退两步，然后正常遍历
          - 从后向前完成复写步操作

			**1. 双指针**
				- cur位于“复写”数位置从左往右遍历
				- dest执行复写指令
			**2. 操作步骤**
				- 判断cur的值
				- dest进行复写数组值
					- cur为非零，直接复写cur所指向的值
					- cur为0，复写0，dest往前走一步，每一步所指向的值都复写为0
				- dest--，cur--;

代码实现

`class Solution {

public:

    void duplicateZeros(vector<int>& arr) {

          int dest=-1;

    int cur = 0;

   int arrSize=arr.size();

 while(cur<arrSize)

 {

    if(arr[cur])

    dest++;

    else dest+=2;

    if(dest>=arrSize-1)

    break;

    cur++;

 }

    if(dest==arrSize)

    {

        arr[arrSize-1]=0;

        cur--;dest-=2;

    }

    //从后向前完成复写操作

    while(cur>=0)

    {

        if(arr[cur])

        arr[dest--]=arr[cur--];

        else

        {

            arr[dest--]=0;

            arr[dest--]=0;

            cur--;

        }

    }

}

};`