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

【蓝桥杯每日一题】双指针算法

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙我与杀戮之中绽放,亦如黎明的花朵🌙
🍉一起加油,去追寻、去成为更好的自己!

蓝桥杯倒计时 41天

文章目录

  • 🍎、双指针算法
  • 🍎、例题分析
        • 🍇、(AcWing)字符串删减
        • 🍇、(AcWing)最长连续不重复子序列
        • 🍇、(AcWing)数组元素的目标和
        • 🍇、(AcWing)判断子序列
  • 🍎、总结

提示:以下是本篇文章正文内容,下面案例可供参考


🍎、双指针算法

🍉、双指针算法的简单概念

双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。

🍉、双指针算法的两个应用场景

两个指针i, j分别指向不同的序列。比如:归并排序的合并过程。
两个指针i, j指向同一个序列。比如:快速排序的划分过程。

在这里插入图片描述

🍉、双指针算法的核心作用

将O(N^2)的时间复杂度优化成为O(N),相当于去掉了一层for循环。

🍉、双指针算法的通用模板

for (int i = 0, j = 0; i < n; i++)
{while (j < i && check(i, j)) j++;// 每道题目的具体逻辑
}

双指针算法为什么能优化掉一层for循环?

因为原来循环两次i,j,我们是通过回溯的方式来实现遍历的,即原来的内层循环j不满足条件时i++, j = 0开始循环。而双指针算法i, j都是具有单调性的(一般是单调递增),因此时间复杂度最多是O(n + m)。


🍎、例题分析

🍇、(AcWing)字符串删减

本题链接: 字符串删减
在这里插入图片描述
简单分析题意:对于长度为n的字符串,我们删除一些字母,使字符串中没用三个或者三个以上的连续的’x’,通过反证法,我们可以得出在最优解中,一定不会删掉’x’以外的字母。设置一个cnt = 0, 来计算每一段x出现的次数,cnt < 3, 操作次数 0, 从cnt >= 3 ,要操作2次
在这里插入图片描述
双指针代码示例:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string str;
int n;
int main ()
{cin >> n >> str;int cnt = 0, res = 0;for(int i = 0; i < n; i++)if(str[i] == 'x'){int j = i + 1;while(j < n && str[j] == 'x') j++;res += max(j - i -2, 0);//如果长度小于0就和0取max,精妙的推算i = j - 1;// i是要跳到j的位置,但是i待会会++,所以i = j - 1}cout << res << endl;return 0;}

模拟代码:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string str;
int n;
int main ()
{cin >> n >> str;int cnt = 0, res = 0;for(int i = 0; i < n; i++)if(str[i] == 'x'){cnt++;if(cnt == 3){cnt -= 1;res++;}}else cnt = 0;cout << res << endl;return 0;}

🍇、(AcWing)最长连续不重复子序列

本题链接: 最长连续不重复子序列
在这里插入图片描述
简单分析思路:
在这里插入图片描述
代码示例:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int s[N],a[N];
int n;
int main()
{int res = 0;cin >> n;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0, j = 0; i < n;i++){s[a[i]]++;while(j < i && s[a[i]] > 1){s[a[j]]--;j++;}res = max(res, i - j + 1);}cout << res << endl;return 0;
}

🍇、(AcWing)数组元素的目标和

本题链接: 数组元素的目标和
在这里插入图片描述
简单分析思路:本题属于两个指针i, j分别指向不同的序列。,如果a[i] + b[j] == x时,输出i,和j,我们从前往后枚举i,从后往前枚举j,如果两者的和>x,就j–,如果刚好等于就输出+break,如果小于就i++。
在这里插入图片描述
代码示例:

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e5 + 10;
int a[N], b[N];
int n, m, x;
int main ()
{cin >> n >> m >> x;for(int i = 0; i < n; i++) cin >> a[i];for(int i  =0; i < m; i++) cin >> b[i];for(int i = 0, j = m - 1; i < n; i++){while(a[i] + b[j] > x && j >= 0){j--;}if(a[i] + b[j] == x){cout << i << " " << j << endl;break;}}return 0;
}

🍇、(AcWing)判断子序列

本题链接: 判断子序列
在这里插入图片描述
在这里插入图片描述
代码示例

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int n, m;
int main ()
{cin >> n >> m;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < m; i++) cin >> b[i];int i = 0, j = 0;while(i < n && j < m){if(a[i]== b[j]) i++;j++;}if(i == n) printf("Yes");else printf("No");return 0;
}

🍎、总结

    本文简要介绍了双指针的简要概念和几道双指针的经典例题,希望大家读后能有所收获!

相关文章:

【蓝桥杯每日一题】双指针算法

&#x1f34e; 博客主页&#xff1a;&#x1f319;披星戴月的贾维斯 &#x1f34e; 欢迎关注&#xff1a;&#x1f44d;点赞&#x1f343;收藏&#x1f525;留言 &#x1f347;系列专栏&#xff1a;&#x1f319; 蓝桥杯 &#x1f319;我与杀戮之中绽放&#xff0c;亦如黎明的花…...

拼数(一般贪心)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 题号&#xff1a;NC16783 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 设有n个正整…...

LeetCode 热题 C++ 169. 多数元素 10. 正则表达式匹配 155. 最小栈

力扣169 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3] 输出&#xff1…...

Clickhouse学习:MergeTree

MergeTree一、MergeTree逻辑存储结构二、MergeTree物理存储结构三、总结一、MergeTree逻辑存储结构 如上图所示,在排序键(CountrID、Date)上做索引,数据会按照这两个字段先后排序ClickHouse是稀疏索引,每隔8192行做一个索引,如(a,1),(a,2),比如想查a,要读取[0,3)之间的内容,稀疏…...

【java基础】包装类,自动装箱和自动拆箱

文章目录基本介绍包装类自动装箱自动拆箱包装类注意事项包装类比较包装器内容不可变基本介绍 有时&#xff0c;需要将int这样的基本类型转换为对象。所有的基本类型都有一个与之对应的类。 例如&#xff0c;Integer类对应基本类型int。通常&#xff0c;这些类称为包装器&#…...

Android笔记(二十五):两种sdk热更插件资源加载方案

背景 在研究sdk插件化热更新方式的过程中总结出了两套插件资源加载方案&#xff0c;在此记录下 资源热更方式 方式一&#xff1a;合并所有插件资源 需要解决资源id冲突问题 资源ID值一共4个字段&#xff0c;由三部分组成&#xff1a;PackageIdTypeIdEntryId PackageId&…...

spring框架--全面详解(学习笔记)

目录 1.Spring是什么 2.Spring 框架特点 3.Spring体系结构 4.Spring开发环境搭建 5.spring中IOC和DI 6.Spring中bean的生命周期 7.Spring Bean作用域 8.spring注解开发 9.Spring框架中AOP&#xff08;Aspect Oriented Programming&#xff09; 10.AOP 实现分类 11.A…...

2023年CDGA考试模拟题库(401-500)

2023年CDGA考试模拟题库(401-500) 401.数据管理战略的SMART原则指的是哪项? [1分] A.具体 、高质量、可操作 、现实、有时间限制 B.具体、可衡量、可检验、现实、有时间限制 C.具体、可衡量、可操作、现实、有时间限制 D.具体、高质量、可检验、现实12-24个月的目标 答…...

软件设计师备考文档

cpu 计算机的基本硬件系统&#xff1a;运算器、控制器、存储器、输入设备、输出设备 cpu负责获取程序指令&#xff0c;对指令进行译码并加以执行 * cpu的功能控制器&#xff08;保证程序正常执行&#xff0c;处理异常事件&#xff09; 程序控制操作控制运算器&#xff08;只能…...

Javascript的API基本内容(一)

一、获取DOM对象 querySelector 满足条件的第一个元素 querySelectorAll 满足条件的元素集合 返回伪数组 document.getElementById 专门获取元素类型节点&#xff0c;根据标签的 id 属性查找 二、操作元素内容 通过修改 DOM 的文本内容&#xff0c;动态改变网页的内容。 inn…...

10、最小公倍数

法一&#xff1a; #include <stdio.h>int main(){int a,b;scanf("%d%d",&a,&b);int m a>b?a:b;//m表示a,b之间的较大值while(1){if(m%a0&&m%b0){break;}m;}printf("%d",m);return 0; }法二&#xff1a;a*i%b0成立 #include &…...

【vue】vue2.x项目中使用md文件

一、Vue项目展示md文件的三种方式 1、将md文件 导入为 html 生成的标题标签自带具有id属性&#xff0c;值为标题内容&#xff1b; <h2 id"测试">测试</h2> # 处理md为html字符串 yarn add markdown-loader # 处理字符串&#xff0c;用于导出显示 yarn a…...

操作系统权限提升(十三)之绕过UAC提权-MSF和CS绕过UAC提权

系列文章 操作系统权限提升(十二)之绕过UAC提权-Windows UAC概述 注&#xff1a;阅读本编文章前&#xff0c;请先阅读系列文章&#xff0c;以免造成看不懂的情况&#xff01;&#xff01; MSF和CS绕过UAC提权 CS绕过UAC提权 拿到一个普通管理员的SHELL,在CS中没有*号代表有…...

快速排序+快速定位

快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中&#xff0c;分治法是一种很重要的算法。字面上的解释是“分而治之”&#xff0c;就是把一个复杂的问题分成两个或更多的相同或相似的子问题&#xff0c;再把子问题分成更小的子问题……直到最后子问题可以…...

nginx http rewrite module 详解

大家好&#xff0c;我是 17。 今天和大家聊聊 nginx http rewrite module 。 简单来说&#xff0c; ngx_http_rewrite_module module 用正则匹配请求&#xff0c;改写请求&#xff0c;然后做跳转。可以是内部跳转&#xff0c;也可以是外部跳转。 学习这个模块的时候&#xf…...

机器学习可解释性一(LIME)

随着深度学习的发展&#xff0c;越来越多的模型诞生&#xff0c;并且在训练集和测试集上的表现甚至于高于人类&#xff0c;但是深度学习一直被认为是一个黑盒模型&#xff0c;我们通俗的认为&#xff0c;经过训练后&#xff0c;机器学习到了数据中的特征&#xff0c;进而可以正…...

CV学习笔记-MobileNet

MobileNet 文章目录MobileNet1. MobileNet概述2. 深度可分离卷积&#xff08;depthwise separable convolution&#xff09;2.1 深度可分离卷积通俗理解2.2 深度可分离卷积对于参数的优化3. MobileNet网络结构4. 代码实现4.1 卷积块4.2 深度可分离卷积块4.3 MobileNet定义4.4 完…...

C++进阶——继承

C进阶——继承 1.继承的概念及定义 面向对象三大特性&#xff1a;封装、继承、多态。 概念&#xff1a; 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特 性的基础上进行扩展&#xff0c;增加功能&#xff0c;这…...

数据结构---单链表

专栏&#xff1a;数据结构 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;从零开始&#xff0c;数据结构&#xff01;&#xff01; 单链表前言顺序表的缺陷链表的概念以及结构链表接口实现打印链表中的元素SLTPrintphead->next!NULL和phead!NULL的区别开辟空间SLTNewNod…...

redis数据结构的底层实现

文章目录一.引言二.redis的特点三.Redis的数据结构a.字符串b.hashc.listd.sete.zset(有序集合)一.引言 redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。 通常使用redis作为缓存中间件来降低数据库的压力&#xff0c;除此…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...