算法每日双题精讲——双指针(移动零,复写零)

🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟

别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧!💪


💯前言

在算法的世界里,双指针技巧常常能发挥出神奇的作用😎。今天,我们就来精讲两道利用双指针解决的经典题目:移动零和复写零。 

📣由于俩道题目均为数组,这里的双指针算法指的是:利用数组下标代替指针

当我们遇到,数组分块,数组划分的问题时,可以考虑使用双指针法。 

 


 💯双指针的作用

✍两个指针的作用:

  • cur:从左往右扫描数组,遍历数组
  • dest:已处理的区间内,非零元素的最后一个位置

分为三个区间:

  1. [0, dest]
  2. [dest + 1,cur -1]
  3. [cur, n -1]

💯移动零

题目链接👉【力扣】 

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

示例:
输入:nums = {0,1,0,3,12}
输出:{1,3,12,0,0}

⭐解题思路:

我们可以使用双指针法来解决这个问题。一个指针 cur用于遍历整个数组,另一个指针dest 用于指向当前非零元素应该放置的位置。当遇到非零元素时,将其放置在dest 指针所指的位置,并将dest 指针向后移动一位。遍历结束后,从dest 指针开始到数组末尾的位置全部设置为零。

 😀俩个指针将数组分为三个区间:

  1. [0, dest]:全是非0的元素(已经处理)
  2. [dest + 1,cur -1]:都是0(已经处理)
  3. [cur, n -1]:还未处理过的

 

 代码实现(以 C++ 为例):
class Solution {
public:void moveZeroes(vector<int>& nums) {// dest 用于标记已处理的非零元素的最后位置int dest = -1;// cur 用于遍历整个向量int cur = 0;while (cur < nums.size()) {// 如果当前位置的元素为 0if (nums[cur] == 0) {cur++;} else {// 先将 dest 加 1,标记下一个非零元素应放置的位置swap(nums[++dest], nums[cur]);cur++;}}}
};
👀复杂度分析:
  • 时间复杂度:O(n),其中 n 是数组的长度。我们只需要遍历一次数组。
  • 空间复杂度:O(1),只使用了有限的额外空间。

💯复写零

题目链接👉【力扣】

题目描述:给你一个长度固定的整数数组 arr,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。注意❗:不要在超过该数组长度的位置写入元素。

示例:
输入:arr = {1,0,2,3,0,4,5,0}
输出:{1,0,0,2,3,0,0,4}

 

解题思路:

同样可以使用双指针法来解决这个问题。一个指针cur用于遍历数组,另一个指针dest用于指向复写零后数组中元素应该放置的位置。当遇到零元素时,将dest指针后的元素依次向后移动两位,并在dest和 dest+1 的位置都放置零。当遇到非零元素时,将其放置在dest指针所指的位置,并将dest指针向后移动一位。

🙋这个解题思路是怎么来的呢? 
  1. 首先我们从左往右遍历数组, 

     

    当arr[cur]!=0时,我们让dest的后面一个的值赋予a[cur]正指向的那个值

    当arr[cur]==0时,我们让dest的后俩个值都赋予0

    当走到这一步时:


    cur找不到下一个为2的值了,因此我们不能从左往右遍
  2. 我们从右往左遍历,dset指向最后一个元素,cur指向最后一个要复写的数
    当a[cur]!=0时,让a[dest]=a[cur],然后cur--,dest--;
    当a[cur]==0时,让a[dest--]=0,a[dest--]=0,cur--;
    这样遍历没有问题,因此我们选择从右往左遍历
    所以我们只要找到最后要“复写”的数即可

⭐找最后一个要复写的数 

 

👇起初让cur指向数组的开头,dest指向-1的位置: 

代码实现(以 C++ 为例): 
class Solution {
public:void duplicateZeros(vector<int>& arr) {// dest 用于标记复制零元素后的新位置,初始值为 -1int dest = -1;// cur 用于遍历原始数组,初始值为 0int cur = 0;int n = arr.size();// 遍历原始数组,确定复制零元素后的新位置while (cur < n) {// 如果当前元素不为 0if (arr[cur]!= 0) {// dest 向后移动一位dest++;} else {// 如果当前元素为 0,dest 向后移动两位(因为要复制一个零)dest += 2;}// 如果 dest 已经到达或超过新数组的最后一个位置,跳出循环if (dest >= n - 1) break;// cur 向后移动一位,继续遍历原始数组cur++;}// 如果 dest 正好等于新数组的长度if (dest == n) {// 将新数组的最后一个位置设为 0arr[n - 1] = 0;// dest 回退两位dest -= 2;// cur 回退一位,因为上一步 cur 多走了一步cur--;}// 从后往前遍历原始数组,进行复制操作while (cur >= 0) {// 如果当前元素不为 0if (arr[cur]!= 0) {// 将当前元素复制到新位置arr[dest] = arr[cur];// cur 和 dest 都向前移动一位cur--;dest--;} else {// 如果当前元素为 0,先将 0 复制到 dest 位置,再将另一个 0 复制到 dest - 1 位置arr[dest--] = 0;arr[dest--] = 0;// cur 向前移动一位cur--;}}}
};
👀复杂度分析:
  • 时间复杂度:O(n),其中 n 是数组的长度。我们需要遍历两次数组。
  • 空间复杂度:O(1),只使用了有限的额外空间。

💯总结

通过这两道题目,我们可以看到双指针算法在处理数组相关问题时的高效性和灵活性👏。希望大家在今后的算法学习中,能够熟练掌握双指针技巧,解决更多复杂的问题💪。


我以后还会对 算法 相关知识进行更多的创作,欢迎大家关注我,一起探索 算法 的奇妙世界😜

👉【A Charmer】

 

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

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

相关文章

数据库的使用02:SQLServer的连接字符串、备份、还原、SQL监视相关设置

目录 一、连接字符串 【本地连接字符串】 【远程连接字符串】 二、备份 三、还原 &#xff08;1&#xff09;还原数据库-bak、btn文件 &#xff08;2&#xff09;附加数据库mdf文件 四、SQL监视器的使用 一、连接字符串 【本地连接字符串】 server DESKTOP-FTH2P3S; Da…

使用SearXNG-搭建个人搜索引擎(附国内可用Docker镜像源)

介绍 SearXNG是聚合了七十多种搜索服务的开源搜索工具。我们可以匿名浏览页面&#xff0c;不会被记录和追踪。作为开发者&#xff0c;SearXNG也提供了清晰的API接口以及完整的开发文档。 部署 我们可以很方便地使用Docker和Docker compose部署SearXNG。下面给出Docker部署Se…

【笔记】LLC电路工作频点选择 2-2 开关管与滤波压力

LLC谐振变换器稳态工作波形分析 - 知乎&#xff0c;上面这篇文的结论相较MPS那篇文章的结论更严格。我们分析一下它的频点选择为什么会更窄&#xff1a; 1. LLC电路模型 电流滞后的特性就是电路呈感性注意这里也是开关管ZVS开通。 2.工作循环的波形 iLm的波形&#xff0c;最终…

mysql数据同步到sql server

准备工作 下载安装sql server express 2019 现在安装SSMS(连接数据库GUI) 安装ssms for mysql 需要注意的是在上面的步骤中首先需要根据指导安装mysql ODBC 设置express sa用户密码登录 --change password for login user "sa"Security > Logins > sa (rig…

【SpringMVC】——Cookie和Session机制

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;实践 1&#xff1a;获取URL中的参数 &#xff08;1&#xff09;PathVariable 2&…

B2119 删除单词后缀

B2119 删除单词后缀 #include <iostream> using namespace std; # include <string.h> #include <ctype.h> #include <algorithm> #include <string.h> int main(){ string word; cin>>word; if(word.size()> 2 && word.…

AlohaKit:一组.NET MAUI绘制的开源控件

前言 今天大姚给大家分享一组.NET MAUI绘制的开源、免费&#xff08;MIT License&#xff09;UI控件库&#xff1a;AlohaKit。 MAUI介绍 .NET MAUI是一个开源、免费&#xff08;MIT License&#xff09;的跨平台框架&#xff08;支持Android、iOS、macOS 和 Windows多平台运…

漫谈分布式唯一ID

文章目录 本系列前言UUIDDB自增主键Redis incr命令号段模式雪花算法 本系列 漫谈分布式唯一ID&#xff08;本文&#xff09;分布式唯一ID生成&#xff08;二&#xff09;&#xff1a;leaf分布式唯一ID生成&#xff08;三&#xff09;&#xff1a;uid-generator分布式唯一ID生成…

C语言:文件操作2(又一万字?)

关于文件操作这章内容&#xff0c;因为知道内容较多所以我分两篇发了&#xff0c;但是还是没料到第二篇还是这么多&#xff0c;达到了一万多字&#xff01;&#xff01;&#xff01;作者本人真的将知识点进行了超级详解分析并且举了很多例子来帮助读者理解&#xff0c;本文章较…

STM32标准库-待机模式

1.1 STM32待机模式简介 STM32单片机具有低功耗模式&#xff0c;包括睡眠、停止和待机三种。 运行状态下&#xff0c;HCLK为CPU提供时钟。HCLK由AHB预分频器分频后直接输出得到。 低功耗模式选择需考虑电源消耗、启动时间和唤醒源。 睡眠模式停CPU不停外设时钟&#xff1b; 停止…

C++内存分区

内存分区 C程序在执行时&#xff0c;将内存大方向划分为4个区域 代码区&#xff1a;存放函数体的二进制代码&#xff0c;由操作系统进行管理的 全局区&#xff1a;存放全局变量和静态变量以及常量&#xff08;不包括局部常量&#xff09; 栈区&#xff1a;由编译器自动分配释…

大数据面试题--kafka夺命连环问

1、kafka消息发送的流程&#xff1f; 在消息发送过程中涉及到两个线程&#xff1a;一个是 main 线程和一个 sender 线程。在 main 线程中创建了一个双端队列 RecordAccumulator。main 线程将消息发送给双端队列&#xff0c;sender 线程不断从双端队列 RecordAccumulator 中拉取…

ElasticSearch备考 -- 集群配置常见问题

一、集群开启xpack安全配置后无法启动 在配置文件中增加 xpack.security.enabled: true 后无法启动&#xff0c;日志中提示如下 Transport SSL must be enabled if security is enabled. Please set [xpack.security.transport.ssl.enabled] to [true] or disable security b…

LeetCode:485.最大连续1的个数——简单题简单做

目录 题目——485.最大连续1的个数 题目分析&#xff1a; 图解如下&#xff1a; 代码如下 题目——485.最大连续1的个数 给定一个二进制数组 nums &#xff0c; 计算其中最大连续 1 的个数。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,0,1,1,1] 输出&#xff1a;3 解…

如何在Android中自定义property

在Android中创建自定义的属性&#xff08;Android property&#xff09;通常用于调试、性能调优或传递应用和系统之间的信息。 以下是如何在Android中创建和使用自定义属性的步骤&#xff1a; 1. 定义属性 在Android中&#xff0c;属性是以“属性名称属性值”形式定义的键值对…

web——sqliabs靶场——第二关

今天来搞第二关&#xff0c;来看看是什么咸蛋 1.判断是否存在sql注入漏洞 输入1 存在sql注入&#xff0c;报错语句为 You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near LIMIT 0,1 …

时序预测 | Python基于CNN-transformer时间序列预测

时序预测 | Python基于CNN-transformer时间序列预测 目录 时序预测 | Python基于CNN-transformer时间序列预测预测效果基本介绍参考资料 预测效果 基本介绍 时序预测 | Python基于CNN-transformer时间序列预测 Cnn-transformer-自适应稀疏自注意力ASSA-对比归一化contranorm预…

windows中docker安装redis和redisinsight记录

创建一个Redis运行容器&#xff0c;命令如下 docker run -it -d --name redis -p 6379:6379 redis --bind 0.0.0.0 --protected-mode no -d 代表Redis容器后台运行 --name redis 给创建好的容器起名叫redis -p 6379:6379 将容器的6379端口映射到宿主机的6379端口&#xff0c;注…

ClickHouse创建账号和连接测试

在之前搭建ClickHouse的时候&#xff0c;把账户相关的去掉了&#xff0c;所以登录和连接的时候是不需要账号密码的&#xff0c;但是实际项目中&#xff0c;肯定是需要根据需要创建账号。 一&#xff0c;创建账号 1&#xff0c;进入到 /etc/clickhouse-server&#xff0c; 编辑…

基于微信小程序实现个人健康管理系统

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…