力扣1089题 复写零 双指针解法

2023-12-01 18:15
文章标签 复写 指针 力扣 解法 1089

本文主要是介绍力扣1089题 复写零 双指针解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2. 复写零

给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

示例 1:

输入:arr = [1,0,2,3,0,4,5,0]
输出:[1,0,0,2,3,0,0,4]
解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]

示例 2:

输入:arr = [1,2,3]
输出:[1,2,3]
解释:调用函数后,输入的数组将被修改为:[1,2,3]

算法思路

本题使用双指针算法.

如果[从前往后]进行原地复写的话, 由于0会复写两次, 导致没有被复写的数被[覆盖]掉了. 因此我们使用[从后向前]的复写策略.

算法流程

  1. 初始化两个指针cur = 0, dest = -1

  2. 先找到最后一个复写的数, 使cur指向最后一个复写的数, dest指向从后往前复写的起始位置, 应该是数组的最后一个元素的位置.

    • cur < arr.length时, 一直执行下面的循环:

      • 先判断cur位置的值

        • 如果为0, dest向后移动2步
        • 如果不是0, dest向后移动1步
      • 判断dest是否已经到达数组的最后一个元素的位置, 如果到达了, 就终止循环.

      • cur++, 继续判断

  3. 处理边界情况. 判断dest是否发生越界(dest = arr.length):

    如果发生了越界:

    • 让数组arr[arr.length - 1] = 0
    • cur--
    • dest -= 2
  4. "从后向前"完成复写操作, 只要cur >= 0

    • 判断cur位置的值
      • 如果是0: destdest - 1位置的值改为0, dest -= 2
      • 如果不是0: dest位置的值改为cur位置的值, dest--
    • cur--

Java代码

class Solution {public static void duplicateZeros(int[] arr) {int cur = 0, dest = -1;while (cur < arr.length) {if(arr[cur] == 0) {dest += 2;} else {dest++;}if(dest >= arr.length - 1) {break;}cur++;}if(dest >= arr.length) {arr[arr.length - 1] = 0;dest -= 2;cur--;}while (cur >= 0) {if(arr[cur] == 0) {arr[dest--] = 0;arr[dest--] = 0;cur--;} else {arr[dest--] = arr[cur--];}}}
}

时间复杂度: O(N) 空间复杂度O(1)

这篇关于力扣1089题 复写零 双指针解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/442184

相关文章

解决java.lang.NullPointerException问题(空指针异常)

《解决java.lang.NullPointerException问题(空指针异常)》本文详细介绍了Java中的NullPointerException异常及其常见原因,包括对象引用为null、数组元... 目录Java.lang.NullPointerException(空指针异常)NullPointer

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【C++】作用域指针、智能指针、共享指针、弱指针

十、智能指针、共享指针 从上篇文章 【C++】如何用C++创建对象,理解作用域、堆栈、内存分配-CSDN博客 中我们知道,你的对象是创建在栈上还是在堆上,最大的区别就是对象的作用域不一样。所以在C++中,一旦程序进入另外一个作用域,那其他作用域的对象就自动销毁了。这种机制有好有坏。我们可以利用这个机制,比如可以自动化我们的代码,像智能指针、作用域锁(scoped_lock)等都是利用了这种机制。

MFC中App,Doc,MainFrame,View各指针的互相获取

纸上得来终觉浅,为了熟悉获取方法,我建了个SDI。 首先说明这四个类的执行顺序是App->Doc->Main->View 另外添加CDialog类获得各个指针的方法。 多文档的获取有点小区别,有时间也总结一下。 //  App void CSDIApp::OnApp() {      //  App      //  Doc     CDocument *pD

C和指针:结构体(struct)和联合(union)

结构体和联合 结构体 结构体包含一些数据成员,每个成员可能具有不同的类型。 数组的元素长度相同,可以通过下标访问(转换为指针)。但是结构体的成员可能长度不同,所以不能用下标来访问它们。成员有自己的名字,可以通过名字访问成员。 结构声明 在声明结构时,必须列出它包含的所有成员。 struct tag {member-list} variable-list ; 定义一个结构体变量x(包含