【蓝桥杯】每天一题，理解逻辑（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--;}}}};`