【算法专题突破】双指针 - 复写零(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的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
99 4
【算法】双指针
【算法】双指针
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
147 68
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。

热门文章

最新文章