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

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 复写零(2)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1. 题目解析

2. 算法原理

3. 代码编写

写在最后:


1. 题目解析

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

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

我先来读题,

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

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

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

2. 算法原理

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

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

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

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

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

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

我们先从左往右试一下:

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

 看起来并不太行:

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

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

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

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

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

然后模拟双指针的过程:

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

cur遇到0就复写两次:

 【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

遇到非 0 就正常写入:

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

以此类推:

【算法专题突破】双指针 - 复写零(2),算法专题训练,c++,算法

 我们发现就成功了,

那现在问题来了,我们怎么得到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--;
            }
        }
    }
};

写在最后:

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

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

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~文章来源地址https://www.toymoban.com/news/detail-679618.html

到了这里,关于【算法专题突破】双指针 - 复写零(2)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法专题突破】双指针 - 四数之和(8)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:18. 四数之和 - 力扣(Leetcode)  这道题跟三数之和也是一样的, 题目很好理解,就是四个数的和等于target的情况, 且这四个数不能重复。 首先还是暴力解法: 排序 + 暴力枚举 + set去重 我们当然是用优化的解法

    2024年02月09日
    浏览(37)
  • 【算法专题突破】双指针 - 三数之和(7)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:15. 三数之和 - 力扣(Leetcode)  题目就是要找出和为0的不重复的三元组, 注意三元组的每个元素是得不同的位置,那不重复又是什么意思呢? 我们可以看第一个示例, 他找出了三个三元组,但是他最后只返回

    2024年02月09日
    浏览(39)
  • 【算法专题突破】双指针 - 盛最多水的容器(4)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:11. 盛最多水的容器 - 力扣(Leetcode)   这道题目也不难理解, 两边的柱子的盛水量是根据短的那边的柱子决定的, 而盛水量就是短的柱子的高度 * 宽度即可。  这道题可以用暴力枚举,两层for循环,肯定是可

    2024年02月10日
    浏览(37)
  • 【算法专题突破】双指针 - 和为s的两个数字(6)

    目录   1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:剑指 Offer 57. 和为s的两个数字 - 力扣(Leetcode)  这道题题目就一句话但是也是有信息可以提取的, 最重要的就是开始的那句话,“递增序列” 然后在数组中找出两个和为s的数即可(而且是任意一对即可)

    2024年02月09日
    浏览(35)
  • 【算法专题突破】双指针 - 有效三角形的个数(5)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:611. 有效三角形的个数 - 力扣(Leetcode)  我们可以根据示例1来理解这一道题目, 他说数组里面的数可以组成三角形三条边的个数, 那我们先自己枚举一下所有情况看看:  【2, 2, 3】  【2, 2, 4】  【2,

    2024年02月10日
    浏览(46)
  • 【算法】活用双指针完成复写零操作

    Problem: 1089. 复写零 首先我们来分析一下本题的题目意思 可以看到题目中给到了一个数组,意思是让我们将数组中的零元素都复写一遍,然后将其余的元素向后平移 光就上面这样来看还是不太形象,我们通过画图来分析一下,通过下图我们可以看到,凡是0的都复写了两遍,凡

    2024年02月11日
    浏览(53)
  • 【算法挨揍日记】day01——双指针算法_移动零、 复写零

    283. 移动零 https://leetcode.cn/problems/move-zeroes/ 题目: 给定一个数组  nums ,编写一个函数将所有  0  移动到数组的末尾,同时保持非零元素的相对顺序。 请注意  ,必须在不复制数组的情况下原地对数组进行操作。    解题思路: 我们可以利用两个指针(dest和cur)的方法,

    2024年02月11日
    浏览(34)
  • 【算法|双指针系列No.2】leetcode1089. 复写零

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月13日
    浏览(40)
  • 【LeetCode 算法专题突破】滑动窗口(⭐)

    学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受 先来一道经典的滑动窗口试试水 题目链接:209. 长度最小的子数组 其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算

    2024年02月07日
    浏览(53)
  • 【算法专题突破】滑动窗口 - 长度最小的子数组(9)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:209. 长度最小的子数组 - 力扣(Leetcode)  要注意的是,题目给的是正整数, 而题目要求并不难理解,就是找最短的子数组。 如果使用暴力的话,就是一个O(N3)的算法,复杂度很高, 我们可以用滑动窗口来做,

    2024年02月09日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包