当前位置: 首页 > news >正文

双指针 (C/C++)

1. 双指针

双指针算法的核心思想:将暴力解法的时间复杂度,通常是O(N*N),通过某种特殊的性质优化到O(N)。

做题思路:先想想暴力解法的思路,然后分析这道题的特殊性质,一般是单调性。然后得出双指针算法的思路。

双指针算法的模板:

for(int i = 0; i <n; i++)

{

        while(j < i && check(i, j))

                j++;

        //具体题目的解题思路

}、

1.1 例题

给定一个长度为 n 的整数序列,请找出最长的不包含重复数数字的最长子序列,输出它的长度。

输入格式

第一行包含整数 n 。

第二行包含 n 个整数(均在0 ~ 100000范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复数字的连续子序列的长度。

数据范围

1 <= n <= 100000

按照上面介绍的解题思路:我们先看看暴力解法怎么做的:两层for循环,外层循环在遍历数组时,对于外层循环遍历的每一个值,内层循环都会从该位置开始去遍历,通过检查区间内是否存在重复数字,更新结果。显然这种解法的事件复杂度为O(N*N)。伪代码如下:

for (int i = 0; i < n; i++)
{
    for (j = i + 1; j < n; j++)
    {
        if (!check(i, j))
            ret = max(ret, i - j + 1);
    }
}

其中n为数组的长度,check为检查区间 [ i, j ] 中的元素是否存在重复的数字,如果不存在更新结果,保存到ret中。

双指针:同样根据上面提供的解题思路,我们尝试从暴力解法中分析出单调性。嗯,双指针的左侧指针在整个查找过程中是单调的。怎么理解呢?

下面以一个具体的例子:1,2,2,3,5 来分析哈:

 现在我们已经知道了双指针的大致思路了,但是好像还没有弄清除单调性从何而来。对于本题单调性就是:在 i++ 向右找更大的满足要求的更长区间时,j不可能存在向前动 (j--) 的情况。即,本题中 j 具有单调性。

 弄清除了这些,我们只需要知到怎么判定一个区间中是否有重复元素就行了。我们可以初始化一个数组a,遍历原数组b, 得到的值假设为s,就让 a[s] + 1,代表这个数字出现了一次。注意当一个区间中没有重复元素时,i++,那么只有原数组中下标为 i 的 的值才会是重复的元素,因此我们只需要判断 a[b[i]] 的值是否是大于 1 即可。这就是模板中的 check 。另外本题中不要 i > j 这个条件,因为 i == j 时,区间 [j, i] 中就没有重复的元素了,i然后就会加一,即 j 是不会大于 i 的。

当区间内存在重复元素时,j++的同时要将 a[b[j]]--,少了一个数字嘛。

 现在可以写代码啦!

int main()
{const int N = 100000;//原数组int b[N];//统计数字出现次数的数组int a[N] = { 0 };//用于保存最大的区间长度int ret = 0;int j = 0;//读入数据int n;scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d", &b[i]);}//核心算法for (int i = 0; i < n; i++){a[b[i]]++;while (a[b[i]] > 1){//少一个数字,次数减一a[b[j]]--;j++;}//更新结果ret = ret > i - j + 1 ? ret : i - j + 1;}//打印结果printf("%d\n", ret);system("pause");return 0;
}

1.2 小试牛刀(来源:Acwing)

相关文章:

双指针 (C/C++)

1. 双指针 双指针算法的核心思想&#xff1a;将暴力解法的时间复杂度&#xff0c;通常是O(N*N)&#xff0c;通过某种特殊的性质优化到O(N)。 做题思路&#xff1a;先想想暴力解法的思路&#xff0c;然后分析这道题的特殊性质&#xff0c;一般是单调性。然后得出双指针算法的思路…...

CVE-2023-23752 Joomla未授权访问漏洞分析

漏洞概要 Joomla 在海外使用较多&#xff0c;是一套使用 PHP 和 MySQL 开发的开源、跨平台的内容管理系统(CMS)。 Joomla 4.0.0 至 4.2.7 版本中的 ApiRouter.php#parseApiRoute 在处理用户的 Get 请求时未对请求参数有效过滤&#xff0c;导致攻击者可向 Joomla 服务端点发送包…...

单通道说话人语音分离——Conv-TasNet(Convolutional Time-domain audio separation Network)

单通道说话人语音分离——Conv-TasNet模型(Convolutional Time-domain audio separation Network) 参考文献&#xff1a;《Conv-TasNet: Surpassing Ideal Time-FrequencyMagnitude Masking for Speech Separation》 1.背景 在真实的声学环境中&#xff0c;鲁棒的语音处理通常…...

华为OD机试真题Python实现【环中最长子串】真题+解题思路+代码(20222023)

环中最长子串 题目 给你一个字符串s,首尾相连成一个环形, 请你在环中找出o字符出现了偶数次最长子字符串的长度. 备注: 1 <= s.lenth <= 5x10^5 s只包含小写英文字母 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 ## 输入 输入是…...

Netcat安装与使用(nc)

Netcat安装与使用1.Netcat简介1.1.Netcat安装1.1.1.安装整体流程1.1.1.1.安装依赖1.1.1.2.安装Netcat1.1.1.3.配置环境变量1.1.1.4.测试1.2.Netcat基本功能1.3.Netcat常用参数2.Netcat用法2.1.前期准备2.2.banner相关信息抓取2.3.端口扫描2.3.1.扫描指定端口2.3.2.扫描指定端口…...

蓝桥杯:聪明的猴子

题目链接&#xff1a;聪明的猴子https://www.lanqiao.cn/problems/862/learning/ 目录 题目描述 输入描述 输出描述 输入输出样例 运行限制 解题思路&#xff1a; 最小生成树 AC代码&#xff08;Java&#xff09;: 课后练习&#xff1a; 题目描述 在一个热带雨林中生存…...

Spring Boot应用如何快速接入Prometheus监控

1. Micrometer简介Micrometer为Java平台上的性能数据收集提供了一个通用的API&#xff0c;它提供了多种度量指标类型&#xff08;Timers、Guauges、Counters等&#xff09;&#xff0c;同时支持接入不同的监控系统&#xff0c;例如Influxdb、Graphite、Prometheus等。可以通过M…...

vscode远程调试python

目的 注意&#xff1a;这里我们想要实现的是&#xff1a;用vscode 使用remote ssh打开project&#xff0c;然后直接在project里面进行debug&#xff0c;而不需要 在本地vscode目录打开一样的project。 假设大家已经会使用remote ssh打开远程服务器的代码了&#xff0c;那么只…...

Spring Boot 框架 集成 Knife4j(内含源代码)

Spring Boot 框架 集成 Knife4j&#xff08;内含源代码&#xff09; 源代码下载链接地址&#xff1a;https://download.csdn.net/download/weixin_46411355/87480176 目录Spring Boot 框架 集成 Knife4j&#xff08;内含源代码&#xff09;源代码下载链接地址&#xff1a;[htt…...

什么蓝牙耳机适合打游戏?打游戏不延迟的蓝牙耳机

为了提升游戏体验&#xff0c;除了配置强悍的主机外&#xff0c;与之搭配蓝牙耳机等外设产品也尤为重要&#xff0c;今天就带大家来了解一下以下几款适合玩游戏&#xff0c;低延迟操作的蓝牙耳机。 第一款&#xff1a;南卡小音舱蓝牙耳机 参考价格&#xff1a;239元 推荐理由…...

【项目设计】高并发内存池(一)[项目介绍|内存池介绍|定长内存池的实现]

&#x1f387;C学习历程&#xff1a;入门 博客主页&#xff1a;一起去看日落吗持续分享博主的C学习历程博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a; 也许你现在做的事情&#xff0c;暂时看不到成果&#xff0c;但不要忘记&…...

初识MySQL下载与安装【快速掌握知识点】

目录 前言 MySQL版本 MySQL类型 MySQL官网有.zip和.msi两种安装形式&#xff1b; MySQL 下载 1、MySQL 属于 Oracle 旗下产品&#xff0c;进入Oracle官网下载 2、点击产品&#xff0c;找到MySQL 3、进入MySQL页面 4、点击Download&#xff08;下载&#xff09;&#x…...

如何终止一个线程

如何终止一个线程 是使用 thread.stop() 吗&#xff1f; public class ThreadDemo extends Thread{Overridepublic void run() {try {Thread.sleep(10000);} catch (InterruptedException e) {e.printStackTrace();}System.out.println("this is demo thread :"Thre…...

上岸!选择你的隐私计算导师!

开放隐私计算 开放隐私计算开放隐私计算OpenMPC是国内第一个且影响力最大的隐私计算开放社区。社区秉承开放共享的精神&#xff0c;专注于隐私计算行业的研究与布道。社区致力于隐私计算技术的传播&#xff0c;愿成为中国 “隐私计算最后一公里的服务区”。183篇原创内容公众号…...

go gin学习记录5

有了前面几节的学习&#xff0c;如果做个简单的web服务端已经可以完成了。 这节来做一下优化。 我们实验了3种SQL写入的方法&#xff0c;但是发现每一种都需要在方法中去做数据库链接的操作&#xff0c;有些重复了。 所以&#xff0c;我们把这部分提取出来&#xff0c;数据库链…...

PyQt5数据库开发2 5.1 QSqlQueryModel

目录 一、Qt窗体设计 1. 新建Qt项目 2. 拷贝4-3的部分组件过来 3. 添加资源文件 4. 创建Action 5. 添加工具栏 6. 创建菜单项 7. 关闭Action的实现 8. 调整布局 8.1 调整两个groupbox的布局 8.3 为窗体设置全局布局 二、代码拷贝和删除 1. 新建项目目录 2. 编译…...

MySQL-redo log和undo log

什么是事务 事务是由数据库中一系列的访问和更新组成的逻辑执行单元 事务的逻辑单元中可以是一条SQL语句&#xff0c;也可以是一段SQL逻辑&#xff0c;这段逻辑要么全部执行成功&#xff0c;要么全部执行失败 举个最常见的例子&#xff0c;你早上出去买早餐&#xff0c;支付…...

阿里云ECS TOP性能提升超20%!KeenTune助力倚天+Alinux3达成开机即用的全栈性能调优 | 龙蜥技术

文/KeenTune SIG01阿里云 ECS 上售卖页新增“应用加速”功能2023年1月12日 阿里云 ECS 的售卖页有了一些新的变化&#xff0c;在用户选择倚天 Alinux3 新建实例时&#xff0c;多了一个新的选项“应用加速”。这个功能是 阿里云 ECS 基于 KeenTune 提供典型云场景的开机即用的全…...

华为OD机试真题Python实现【快递业务站】真题+解题思路+代码(20222023)

快递业务站 题目 快递业务范围有 N 个站点,A 站点与 B 站点可以中转快递,则认为 A-B 站可达, 如果 A-B 可达,B-C 可达,则 A-C 可达。 现在给 N 个站点编号 0、1、…n-1,用 s[i][j]表示 i-j 是否可达, s[i][j] = 1表示 i-j可达,s[i][j] = 0表示 i-j 不可达。 现用二维…...

【c语言】预处理

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a;> c语言学习 &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...