【算法挨揍日记】day01——双指针算法_移动零、 复写零

 283.移动零 

283. 移动零icon-default.png?t=N6B9https://leetcode.cn/problems/move-zeroes/

题目:

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

 

 解题思路:

我们可以利用两个指针(dest和cur)的方法,将这个数组分为三个区域

我们可以将dest初始化为-1,cur初始化为0

 cur走一遍数组遇到的两种情况:

  • cur位置为0
  • cur位置为非0

当cur位置为0,cur++;

当cur不为0时,swap交换一下就好,dest++;

解题代码:

class Solution {
public:void moveZeroes(vector<int>& nums) {int dest=-1;int cur=0;int size=nums.size();while(cur<size){if(nums[cur]!=0){swap(nums[dest+1],nums[cur]);++dest;}++cur;}}
};

1089. 复写零

1089. 复写零icon-default.png?t=N6B9https://leetcode.cn/problems/duplicate-zeros/

 题目:

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

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

 解题思路:

 本题要求我们要就地修改,不能使用额外的数组,我们先用额外的数组想一想

我们发现结果是这样的

 我们再将使用额外数组的双指针方法用在本地去实验一下,我们发现dest=-1和cur=0,去正向解决问题不可以,会有元素被覆盖丢失的问题!

我们试着反向去操作呢,dest=size-1(指向最后一个元素),那我们如何确定cur的位置呢?

我们可以再利用一次双指针的方法来确认cur的位置,一开始cur=0,dest=-1

遍历数组,当cur遇到0时,dest+=2;当cur遇到非0时,cur++;

这里会有一种边界情况需要我们去考虑:

示例:1 0 2 3 0

我们通过上述方式来确定cur时,会出现以下这种情况:

会出现dest越界的情况,我们考科一让size-1的位置置为0,然后cur--,dest-=2这样就可以解决问题了

然后从后向前遇到0就是置两次0,遇到非0就是复制咯,这一步简单

 

 解题代码:

class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest=-1;int cur=0;int size=arr.size();//确认cur的位置while(cur<size){if(arr[cur]==0)dest+=2;else dest++;if(dest>=size-1)break;cur++;}//边界情况,示例:1 0 2 3 0,当dest的位置越界了if(dest==size){arr[size-1]=0;dest-=2;cur--;}while(cur>=0){if(arr[cur]!=0){arr[dest--]=arr[cur--];}else {arr[dest--]=0;arr[dest--]=0;cur--;}}}
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/85144.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Xcode升级导致关联库报错

想办法找到对应的库 然后到 Build Phases -- LinkBinary With Libraries中点击&#xff0c;选择对应的framework即可&#xff0c;就像我工程的报错 Undefined symbol: _OBJC_CLASS_$_ADClient _OBJC_CLASS_$_ASIdentifierManager 缺失的库是AdSupport.framework 添加后再次编…

【服务平台】Rancher运行和管理Docker和Kubernetes,提供管理生产中的容器所需的整个软件堆栈

Rancher是一个开源软件平台&#xff0c;使组织能够在生产中运行和管理Docker和Kubernetes。使用Rancher&#xff0c;组织不再需要使用一套独特的开源技术从头开始构建容器服务平台。Rancher提供了管理生产中的容器所需的整个软件堆栈。  完整软件堆栈 Rancher是供采用容器的团…

Git全栈体系(五)

第八章 IDEA 集成 GitHub 一、设置 GitHub 账号 如果出现 401 等情况连接不上的&#xff0c;是因为网络原因&#xff0c;可以使用以下方式连接&#xff1a; 然后去 GitHub 账户上设置 token。 点击生成 token。 复制红框中的字符串到 idea 中。 点击登录。 二、分享工程…

数据结构顺序表

今天主要讲解顺序表&#xff0c;实现顺序表的尾插&#xff0c;头插&#xff0c;头删&#xff0c;还有尾删等操作&#xff0c;和我们之前写的通讯录的增删查改有类似的功能。接下来让我们开始我们的学习吧。 1.线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特…

allegro中不可选时,如何对find进行可选操作

allegro出现不可选时&#xff0c;只能尝试其他单一的操作&#xff0c;但这样效率不高&#xff1b;可以通过菜单栏Display下拉菜单点击Element&#xff0c;即可实现FIND下选择需要调整的选项。

022 - STM32学习笔记 - 扩展外部SDRAM(一) - 初识SDRAM和FMC

022 - STM32学习笔记 - 扩展外部SDRAM&#xff08;一&#xff09; - 初识SDRAM和FMC 之前学习了I2C读写EEPROM和SPI读写FLASH&#xff0c;学完之后在学习一种新的存储介质–SDRAM。 一、初识SDRAM 我们知道在stm32内部是有一定大小的SRAM&#xff08;256Kb&#xff09;和FLA…

【Cartopy】库的安装和瓦片加载(天地图、高德等)

原文作者&#xff1a;我辈李想 版权声明&#xff1a;文章原创&#xff0c;转载时请务必加上原文超链接、作者信息和本声明。 Cartopy基础入门 【Cartopy】库的安装和天地图瓦片加载 【Cartopy】【Cartopy】如何更好的确定边界显示 【Cartopy】【Cartopy】如何丝滑的加载Geojso…

100G光模块的应用案例分析:电信、云计算和大数据领域

100G光模块是一种高速光模块&#xff0c;由于其高速率和低延迟的特性&#xff0c;在电信、云计算和大数据领域得到了广泛的应用。在本文中&#xff0c;我们将深入探讨100G光模块在这三个领域的应用案例。 一、电信领域 在电信领域&#xff0c;100G光模块被广泛用于构建高速通…

机器学习深度学习——卷积的多输入多输出通道

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位即将上大四&#xff0c;正专攻机器学习的保研er &#x1f30c;上期文章&#xff1a;机器学习&&深度学习——从全连接层到卷积 &#x1f4da;订阅专栏&#xff1a;机器学习&&深度学习 希望文章对你们有所帮…

4用opencv玩转图像2

opencv绘制文字和几何图形 黑色底图 显示是一张黑色图片 使用opencv画圆形 #画一个圆 cv2.circle(imgblack_img,center(400,400),radius100,color(0,0,255),thickness10) 画实心圆 只需要把thickness-1。 cv2.circle(imgblack_img,center(500,600),radius50,color(0,0,255),t…

Spark(39):Streaming DataFrame 和 Streaming DataSet 输出

目录 0. 相关文章链接 1. 输出的选项 2. 输出模式(output mode) 2.1. Append 模式(默认) 2.2. Complete 模式 2.3. Update 模式 2.4. 输出模式总结 3. 输出接收器(output sink) 3.1. file sink 3.2. kafka sink 3.2.1. 以 Streaming 方式输出数据 3.2.2. 以 batch …

R语言4_安装BayesSpace

环境Ubuntu22/20, R4.1 你可能会报错说你的R语言版本没有这个库&#xff0c;但其实不然。这是一个在Bioconductor上的库。 同时我也碰到了这个问题&#xff0c;ERROR: configuration failed for package systemfonts’等诸多类似问题&#xff0c;下面的方法可以一并解决。 第…

数据结构刷题训练——链表篇(二)

目录 前言 1.题目一&#xff1a;链表分割 1.1 思路 1.2 分析 1.3 题解 2. 题目二&#xff1a;相交链表 2.1 思路 2.2 分析 2.3 题解 3. 题目三&#xff1a;环形链表 3.1 思路 3.2 分析 3.3 题解 总结 前言 本期继续分享链表相关的OJ题目&#xff0c;在这个专栏博客…

elasticsearch简单入门语法

基本操作 创建不同的分词器 ik_smart&#xff1a; 极简分词 &#xff1b; ik_max_word: 最细力再度分词 基本的rest命令 methodurl地址描述PUTlocalhost:9200/索引名称/类型名称/文档id创建文档&#xff08;指定文档id&#xff09;POSTlocalhost:9200/索引名称/类型名称创建文…

蝉妈妈:2023年抖音电商半年报(附下载)

关于报告的所有内容&#xff0c;公众【营销人星球】获取下载查看 核心观点 平台流量竞争从愈发激烈变为趋于愈加缓和商家直攝总时长与观众君播总时长的总体趋势并没有愈加激烈&#xff0c;从23年上半年各自流量的同比增速来看&#xff0c;观众看摄总时长增速高于商家直攝总时…

电脑合上盖子无线网络不会断开

控制面板\硬件和声音\电源选项\系统设置 最终选择不会采取任何操作 选择不会采取任何操作

Cocos Creator的 Cannot read property ‘applyForce‘ of undefined报错

序&#xff1a; 1、博主是看了这个教程操作的时候出的bug>游戏开发 | 17节课学会如何用Cocos Creator制作3D跑酷游戏 | P9 代码控制对象移动_哔哩哔哩_bilibili 2、其实问题不是出在代码上&#xff0c;但是发现物体就是不平移 3、node全栈的资料》node全栈框架 正文…

逆向破解学习-雷电星海战歌

apk 雷电星海战歌 https://download.csdn.net/download/AdrianAndroid/88200826 安装apk&#xff0c;并试玩 # 通过关键字搜索jad 找到统一支付接口 找到匿名内部类的名称 Hook代码 public class HookComAstPlane extends HookImpl {Overridepublic String packageNam…

竞赛项目 深度学习手势识别算法实现 - opencv python

文章目录 1 前言2 项目背景3 任务描述4 环境搭配5 项目实现5.1 准备数据5.2 构建网络5.3 开始训练5.4 模型评估 6 识别效果7 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习手势识别算法实现 - opencv python 该项目较为新颖…

LeetCode 31题:下一个排列

目录 题目 思路 代码 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序…