leetcode经典【双指针】例题

删除有序数组中的重复项: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

解题思路:

首先注意数组是有序的,那么重复的元素一定会相邻。

注: 要求删除重复元素,实际上就是将不重复的元素移到数组的左侧

考虑用 2 个指针,一个在前记作 p,一个在后记作 q,算法流程如下:

首先 :比较 p 和 q 位置的元素是否相等。

如果相等,q 后移 1 位
如果不相等,将 q 位置的元素复制到 p+1 位置上,p 后移一位,q 后移 1 位
重复上述过程,直到 q 等于数组长度。

返回 p + 1,即为新数组长度。

之前在leetcode题解评论区看到大佬,把题目改编一下(本人觉得非常形象,更适合新手小白理解的版本):

题目:外面有宝,赶紧捡回来按序放好,不能重样哟 有点像小夫妻俩,老公q在外面淘宝,找到后运回来,找到一个新的宝,老婆p在家里就给挖个新坑放好,最后外面没宝了,就结束咯

中间对话:

老公:老婆,这个家里有没?(if) 老婆:有了。(nums[p] == nums[q])你再找找(q++)

老公:老婆,这个家里有没?(if) 老婆:有了。(nums[p] == nums[q])你再找找(q++)

老公:老婆,这个家里有没?(if) 老婆:这个没有,拿回来吧 (nums[p] != nums[q]) 放好了,我到下一个位置等你(p++) 你再继续找吧(q++)

貌似双指针都可以这么理解

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int p = 0, q = 1;
        while (q < nums.size()) {
            if (nums[p] == nums[q]) {
                q++;
            } 
            else {
                nums[p+1]=nums[q];
                p++;
                q++;
            }
        }
        return p+1;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

18.标题统计

题目 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);String str sc.nextLine();int res 0;for(int i0;i<str.length();i) {char c str.charAt(i);if(c! && c!\n) {res;}}System.o…

BUUCTF--pwnable_start1

查看保护&#xff1a; 32位程序保护全没开&#xff0c;黑盒测试下效果&#xff1a; 存在栈溢出&#xff0c;那么这题的想法就是直接ret2shellcode了。IDA中看看具体流程&#xff1a; 出奇的少&#xff0c;这题不能看反汇编的代码&#xff0c;直接去看汇编&#xff1a; 主要就2个…

sql——窗口范围之partition by 与 order by

partition by 关键字 partition by 在开窗函数中&#xff0c;常用于表示某个分区&#xff0c;规则了数据的范围 order by 关键字 order by 常用于对分区内的数据进行排序&#xff0c;常见的情况下&#xff0c;order by还能规定sql语句的影响范围。 rows between unbounded …

kannegiesser触摸屏维修CTT-11 4PP420.1043-K37

贝加莱触摸屏维修4PP420.1043-K37 kannegiesser工控机触摸屏维修CTT-11 工控机触摸屏维修常见故障现象 1、工控机开机有显示&#xff0c;但是屏幕很暗&#xff0c;用调亮度功能键调试无任何变化&#xff1b; 2、工控机开机触摸屏白屏或花屏&#xff0c;但是外接显示器正常&a…

机器学习(四) -- 模型评估(3)

系列文章目录 机器学习&#xff08;一&#xff09; -- 概述 机器学习&#xff08;二&#xff09; -- 数据预处理&#xff08;1-3&#xff09; 机器学习&#xff08;三&#xff09; -- 特征工程&#xff08;1-2&#xff09; 机器学习&#xff08;四&#xff09; -- 模型评估…

【JAVA】volatile 关键字的作用

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a; JAVA ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 volatile 的作用&#xff1a; 结语 我的其他博客 前言 在多线程编程中&#xff0c;保障数据的一致性和线程之间的可见性是…

优化|PLSA理论与实践

PLSA又称为概率潜在语义分析&#xff0c;是一种利用概率生成模型对文本集合进行话题分析的无监督学习方法。该模型最大的特点是加入了主题这一隐变量&#xff0c;文本生成主题&#xff0c;主题生成单词&#xff0c;从而得到单词-文本共现矩阵。本文将对包含物理学、计算机科学、…

嵌入式(五)通信协议 | 串行异步同步 UART SPI I2C 全解析

文章目录 0 串口通信协议1 通用异步收发传输器 UART1.1 串口配置1.2 串口初始化1.3 串口发送和接收方式1.3.1 轮询方式发送1.3.2 中断方式发送1.3.3 查询方式接收1.3.4 中断方式接收 2 串行外设接口 SPI2.1 标准的四线SPI接口2.2 SPI的四种模式2.3 配置2.4 发送和接收Master向S…

[python]gym安装报错ERROR: Failed building wheel for box2d-py

报错截图&#xff1a; box2d是一个游戏领域的2D图形C引擎&#xff0c;用来模拟2D刚体物体运动和碰撞。 swig是一个将c/c代码封装为Python库的工具&#xff08;是Python调用c/c库的一种常见手段&#xff09;&#xff0c;所以在运行时box2d会依赖到swig。而swig并不是一个python库…

C#,简单选择排序算法(Simple Select Sort)的源代码与数据可视化

排序算法是编程的基础。 常见的四种排序算法是&#xff1a;简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显&#xff0c;一般使用递归方式实现&#xff0c;但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。本文搜集发布四种算法…

港口车路协同系统方案

目前&#xff0c;国内自动驾驶应用的两种主流路线是单车智能、单车智能V2X。国内多数港口仍采用4G通信技术&#xff0c;单车智能在港口应用的稳定性较差&#xff0c;比如可能受到金属集装箱干扰及移动通信速率不稳定的影响。单车智能V2X将降低对通信速率的要求&#xff0c;可以…

【BCC动态跟踪PostgreSQL】

BPF Compiler Collection (BCC)是基于eBPF的Linux内核分析、跟踪、网络监控工具。其源码存放于GitCode - 开发者的代码家园 想要监控PostgreSQL数据库的相关SQL需要在编译PostgreSQL的时候开启dtrace。下文主要介绍几个和PostgreSQL相关的工具,其他工具可根据需求自行了解。 …

移动通信原理与关键技术学习(第四代蜂窝移动通信系统)

前言&#xff1a;LTE 标准于2008 年底完成了第一个版本3GPP Release 8的制定工作。另一方面&#xff0c;ITU 于2007 年召开了世界无线电会议WRC07&#xff0c;开始了B3G 频谱的分配&#xff0c;并于2008 年完成了IMT-2000&#xff08;即3G&#xff09;系统的演进——IMT-Advanc…

Leetcode 剑指 Offer II 060. 前 K 个高频元素

题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定一个整数数组 nums 和一个整数 k &#xff0c;请返回其中出现…

缘分的计算

题目描述&#xff1a; 缘分是一个外国人难以理解的中文名词。大致说来&#xff0c;缘分是一种冥冥中将两人&#xff08;通常是情人&#xff09;结合的力量。仅管这是种迷信&#xff0c;很多人——特别是女生——喜欢去计算它。 不幸的是&#xff0c;644 也是这样。有天&#x…

【linux笔记】top、ps

【linux笔记】top命令 top&#xff08;Table of process&#xff09;是动态变化的。而ps是静态的。 PID — 进程id USER — 进程所有者 PR — 进程优先级 NI — nice值。负值表示高优先级&#xff0c;正值表示低优先级 VIRT — 进程使用的虚拟内存总量&#xff0c;单位kb。VI…

二叉树的最大深度,力扣

目录 题目地址&#xff1a; 题目&#xff1a; 我们直接看题解吧&#xff1a; 快速理解题解小建议&#xff1a; 审题目事例提示&#xff1a; 解题方法&#xff1a; 解题方法分析&#xff1a; 方法1后序遍历&#xff08;DFS&#xff09; 解题分析&#xff1a; 解题思路&#xff1…

启动 Mac 时显示闪烁的问号

启动 Mac 时显示闪烁的问号 如果启动时在 Mac 屏幕上看到闪烁的问号&#xff0c;这意味着你的 Mac 无法找到自身的系统软件。 如果 Mac 启动时出现闪烁的问号且无法继续启动&#xff0c;请尝试以下步骤。 1.通过按住其电源按钮几秒钟来关闭 Mac。 2.按一下电源按钮&#xf…

强化学习5——动态规划初探

动态规划具体指的是在某些复杂问题中&#xff0c;将问题转化为若干个子问题&#xff0c;并在求解每个子问题的过程中保存已经求解的结果&#xff0c;以便后续使用。实际上动态规划更像是一种通用的思路&#xff0c;而不是具体某个算法。 在强化学习中&#xff0c;被用于求解值函…

华为MDC610接口说明

1、MDC610对外功能接口 2、1、MDC610硬件技术规格