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

用户11367452

发布于 2025-03-06 08:53:09

4400

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

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

@[TOC]

题目解析

算法原理（双指针）

在数组中操作元素的题目，一般都用双指针算法
- 现根据“异地”操作，再优化双指针下的“就地”操作
  - 例子
  - 定义两个指针cur和dest，分别指向两个数组的开头，当cur识别非零元素直接拷贝到dest指向的数组，遇到0元素直接写两遍，直到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--;

        }

    }

}

};`

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-03-05，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode