当前位置: 首页 > 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;是…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...