【算法专题突破】双指针 - 复写零(2)

简介: 【算法专题突破】双指针 - 复写零(2)

1. 题目解析

题目链接:1089. 复写零 - 力扣(Leetcode)

我先来读题,

题目的意思非常的简单,其实就是,

遇到 0 就复制一个写进数组,然后右边的元素就右移一位,

看一眼例子可以很容易理解题意。

2. 算法原理

一般像这种需要移动数组的元素的题目,

也非常常用双指针算法来解题。

这道题如果不使用原地算法,会非常简单,

一个指针遍历原数组,一个指针遍历新数组,

遇到非 0 就直接写进数组,遇到 0 就写两个0进数组即可。

而如果我们想把这个算法优化成原地呢?

我们先从左往右试一下:

看起来并不太行:

会出现全部都复写成0的情况,因为原来的数被修改了,

那我们可以试试从后往前的思路:

我们让cur 指向最后一次写入的位置:

然后模拟双指针的过程:

cur遇到0就复写两次:

遇到非 0 就正常写入:

以此类推:

我们发现就成功了,

那现在问题来了,我们怎么得到cur的起始位置,

或者说我们该怎么得到最后一次写入的位置?

我们可以用 cur 和 dest 两个指针来模拟写入的过程,是的,又是双指针:

1. 判断cur位置是 0 还是 非0

2. dest根据cur位置的值决定走一步还是走两步

3. 判断dest是否已经走到结尾了

4. 如果没到结尾就cur++,如果已经走到结尾了那cur指向的位置就是最后一次写入的数

不过要小心dest的越界问题,如果走到倒数第二个数的时候,cur走到0,

dest往后走两步就会出现越界的问题。我们到时候让cur后退一步,dest后退两步就行。

3. 代码编写

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int dest = -1, cur = 0, size = arr.size();
        // 找到最后一次写入的位置
        while(cur < size) {
            if(arr[cur]) dest++;
            else dest += 2;
            if(dest >= size - 1) break; //走完了
            cur++;
        }
        // 控制边界
        if(dest == size) { //这种就是最后一步是0,走了两步dest越界的情况
            arr[size - 1] = 0;
            dest -= 2;
            cur--;
        }
        // 从后往前做写入操作
        while(cur >= 0) {
            if(arr[cur]) arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

目录
打赏
0
0
0
0
339
分享
相关文章
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
125 4
【算法】双指针
【算法】双指针
基于生物地理算法的MLP多层感知机优化matlab仿真
本程序基于生物地理算法(BBO)优化MLP多层感知机,通过MATLAB2022A实现随机数据点的趋势预测,并输出优化收敛曲线。BBO模拟物种在地理空间上的迁移、竞争与适应过程,以优化MLP的权重和偏置参数,提升预测性能。完整程序无水印,适用于机器学习和数据预测任务。
基于LSB最低有效位的音频水印嵌入提取算法FPGA实现,包含testbench和MATLAB对比
本项目展示了一种基于FPGA的音频水印算法,采用LSB(最低有效位)技术实现版权保护与数据追踪功能。使用Vivado2019.2和Matlab2022a开发,完整代码含中文注释及操作视频。算法通过修改音频采样点的最低有效位嵌入水印,人耳难以察觉变化。然而,面对滤波或压缩等攻击时,水印提取可能受影响。该项目运行效果无水印干扰,适合实时应用场景,核心逻辑简单高效,时间复杂度低。
基于GA遗传算法的拱桥静载试验车辆最优布载matlab仿真
本程序基于遗传算法(GA)实现拱桥静载试验车辆最优布载的MATLAB仿真,旨在自动化确定车辆位置以满足加载效率要求(0.95≤ηq≤1.05),目标是使ηq尽量接近1,同时减少车辆数量和布载耗时。程序在MATLAB 2022A版本下运行,展示了工况1至工况3的测试结果。通过优化模型,综合考虑车辆重量、位置、类型及车道占用等因素,确保桥梁关键部位承受最大荷载,从而有效评估桥梁性能。核心代码实现了迭代优化过程,并输出最优布载方案及相关参数。
基于MobileNet深度学习网络的活体人脸识别检测算法matlab仿真
本内容主要介绍一种基于MobileNet深度学习网络的活体人脸识别检测技术及MQAM调制类型识别方法。完整程序运行效果无水印,需使用Matlab2022a版本。核心代码包含详细中文注释与操作视频。理论概述中提到,传统人脸识别易受非活体攻击影响,而MobileNet通过轻量化的深度可分离卷积结构,在保证准确性的同时提升检测效率。活体人脸与非活体在纹理和光照上存在显著差异,MobileNet可有效提取人脸高级特征,为无线通信领域提供先进的调制类型识别方案。