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

算法基础学习|双指针算法

双指针算法

代码模板

for (int i = 0, j = 0; i < n; i ++ ){while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑
}
常见问题分类:(1) 对于一个序列,用两个指针维护一段区间(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

例题一:最长连续不重复子序列

题目

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

输入格式

第一行包含整数 n

第二行包含 n 个整数(均在 0 \sim 10^5 范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围

1\leq n\leq 10^5

输入样例

5
1 2 2 3 5

输出样例

3

代码示例

#include <iostream>
using namespace std;const int N = 100010;int a[N], s[N];int main(){int n;cin >> n;for(int i = 0; i < n; i++) cin >> a[i];//双指针运算int res = 0;for(int i = 0, j = 0; i < n; i++){s[a[i]]++;while(j < i && s[a[i]] > 1) s[a[j++]]--;//先--后++res = max(res, i - j + 1);}cout << res << endl;
}

例题二:数组元素的目标和

题目

给定两个升序排序的有序数组 A 和 B,以及一个目标值 x

数组下标从 0 开始。

请你求出满足 A[i]+B[j] = x 的数对 (i, j)

数据保证有唯一解。

输入格式

第一行包含三个整数 n, m, x,分别表示 A 的长度,B 的长度以及目标值 x

第二行包含 n 个整数,表示数组 A

第三行包含 m 个整数,表示数组 B

输出格式

共一行,包含两个整数 i 和 j

数据范围

数组长度不超过 10^5
同一数组内元素各不相同。
1\leq 数组元素\leq 10^9

输入样例

4 5 6
1 2 4 7
3 4 6 8 9

输出样例

1 1

代码示例

#include <iostream>
using namespace std;const int N = 100010;int a[N], b[N];int main() {int n, m, x;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 (j >= 0 && a[i] + b[j] > x) j--;//时间复杂度为O(m+n)if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;}}

例题三:判断子序列

题目

给定一个长度为 n 的整数序列 a_1,a_2,...,a_n 以及一个长度为 m 的整数序列 b_1,b_2,...,b_n

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 \left \{ a_1,a_3,a_5 \right \} 是序列 \left \{ a_1,a_2,a_3,a_4,a_5 \right \} 的一个子序列。

输入格式

第一行包含两个整数 n,m

第二行包含 n 个整数,表示 a_1,a_2,...,a_n

第三行包含 m 个整数,表示 b_1,b_2,...,b_n

输出格式

如果 a 序列是 b 序列的子序列,输出一行 Yes

否则,输出 No

数据范围

1\leq n\leq m\leq 10^5,
-10^9\leq a_i,b_i\leq 10^9

输入样例

3 5
1 3 5
1 2 3 4 5

输出样例

Yes

代码示例

#include <iostream>
using namespace std;const int N = 100010;int a[N], b[N];int main() {int n, m;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) cout << "Yes" << endl;else cout << "No" << endl;
}

相关文章:

算法基础学习|双指针算法

双指针算法 代码模板 for (int i 0, j 0; i < n; i ){while (j < i && check(i, j)) j ;// 具体问题的逻辑 } 常见问题分类&#xff1a;(1) 对于一个序列&#xff0c;用两个指针维护一段区间(2) 对于两个序列&#xff0c;维护某种次序&#xff0c;比如归并…...

4.远程登录服务

目录 1. 简介 1.1. 概念 1.2. 功能: 1.3. 分类 1.3.1. 文字接口: 1.3.2. 图形接口&#xff1a; 1.4. 文字接口连接服务器: 2. 连接加密技术简介 2.1. 密钥解析&#xff1a; 3. SSH工作过程&#xff1a; 3.1. 版本协商阶段 3.2. 密钥和算法协商阶段 3.3. 认证阶段(两…...

代码随想录算法训练营第二十九天| 491.递增子序列、46.全排列、47.全排列 II

491.递增子序列 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 解题思路&#xff1a;同层相同元素要跳过 java&#xff1a; class Solution {List<List<Integer>> resultnew ArrayList<>();List<Integ…...

基于若依的ruoyi-nbcio流程管理系统一种简单的动态表单模拟测试实现(五)

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a; https://gitee.com/nbacheng/n…...

多场景建模:阿里多场景多任务元学习方法M2M

multi-scenario multi-task meta learning approach (M2M) 背景 广告领域大部分是针对用户建模的&#xff0c;像点击率预估&#xff0c;很少有针对广告主需求建模&#xff08;广告消耗预估、活跃率/流失率预估、广告曝光量预估&#xff09;&#xff0c;广告的类型较多&#x…...

仿真机器人-深度学习CV和激光雷达感知(项目2)day03【机器人简介与ROS基础】

文章目录 前言机器人简介机器人应用与前景机器人形态机器人的构成 ROS基础ROS的作用和特点ROS的运行机制ROS常用命令 前言 &#x1f4ab;你好&#xff0c;我是辰chen&#xff0c;本文旨在准备考研复试或就业 &#x1f4ab;本文内容是我为复试准备的第二个项目 &#x1f4ab;欢迎…...

【多商户开源-BSD- Fecmall 电商平台】

关于Fecmall Fecmall 关于&#xff0c;Fecmall介绍 Fecbbc开源BSD多商户系统&#xff0c;真正开源&#xff0c;商用免费授权的多商户系统 Fecmall系统简介&#xff1a; 全称为Fancy ECommerce Shop&#xff0c; 着重于电商架构的研发优化&#xff0c;全新定义商城的架构体系&…...

2023春秋杯冬季赛 --- Crypto wp

文章目录 前言Cryptonot_wiener 前言 比赛没打&#xff0c;赛后随便做一下题目 Crypto not_wiener task.py: from Crypto.Util.number import * from gmpy2 import * import random, os from hashlib import sha1 from random import randrange flagb x bytes_to_long(f…...

ImageMagick使用手册

ImageMagick使用手册 文章目录 ImageMagick使用手册ImageMagick是什么指令总结1.查看版本2.官网验证指令解读3.svg转png4.png转ico5.将指定文件夹中的所有PNG图像转换为ICO图标 本教程持续更新&#xff0c;我学到多少就更新多少。关于ffmpeg如何安装可以看上一篇博客win系统环境…...

嵌入式培训机构四个月实训课程笔记(完整版)-C++和QT编程第五天-Qt编程技巧若干解答(物联技术666)

链接&#xff1a;https://pan.baidu.com/s/1-u7GvgM0TLuiy9z7LYQ80Q?pwd1688 提取码&#xff1a;1688 QT在Windows下制作图表 QT是跨平台的程序设计库&#xff0c;在windows下的程序往往想要有一个好看的图标&#xff0c;方法如下&#xff1a; 1.准备个ICO图标。例如&…...

【蓝桥杯选拔赛真题59】python小写字母 第十五届青少年组蓝桥杯python 选拔赛比赛真题解析

目录 python小写字母 一、题目要求 1、编程实现 2、输入输出...

代码随想录算法训练营Day37|738.单调递增的数字、贪心算法总结

目录 738.单调递增的数字 方法一&#xff1a;暴力解法 方法二&#xff1a;贪心解法 贪心算法总结 738.单调递增的数字 题目链接 文章链接 方法一&#xff1a;暴力解法 class Solution { private:// 各位递增判断函数bool checkNum(int num) {int max 10;while (num) {int …...

笔记-影响力-对比,互惠,赌徒原理

笔记 From 《影响力》 目录 C1 影响力的武器 C2:互惠 C3 承诺和一致 C4:社会认同 C5:喜好 C6:权威 C7:稀缺 Ankie的笔记&#xff1a;对比&#xff0c;互惠&#xff0c;赌徒原理 C1 影响力的武器 人类在认知方面有个原理&#xff0c;叫“对比原理”。 假设有人走进一…...

PIL、cv2、numpy,和pytorch(torch)之间的转换

在图像处理和深度学习中&#xff0c;经常需要在PIL&#xff08;Python Imaging Library&#xff09;、OpenCV&#xff08;cv2&#xff09;、NumPy和PyTorch之间进行图像数据的转换。下面是这些库之间常见的转换方法。 1. PIL和numpy之间的转换 import numpy as np from PIL i…...

Java面试题50道

文章目录 1.谈谈你对Spring的理解2.Spring的常用注解有哪些3.Spring中的bean线程安全吗4.Spring中的设计模式有哪些5.Spring事务传播行为有几种6.Spring是怎么解决循环依赖的7.SpringBoot自动配置原理8.SpringBoot配置文件类型以及加载顺序9.SpringCloud的常用组件有哪些10.说一…...

电脑怎么剪辑视频?这些软件不可错过

电脑怎么剪辑视频&#xff1f;随着视频时代的到来&#xff0c;越来越多的人开始涉足视频制作。从Vlog到短片&#xff0c;再到专业级的影视作品&#xff0c;视频已经成为了我们生活中不可或缺的一部分。那么&#xff0c;如何才能快速掌握视频剪辑技巧&#xff0c;制作出令人惊叹…...

HBase学习七:Compaction

1、简介 Compaction是从一个Region的一个Store中选择部分HFile文件进行合并。其目的为了减少 HFile 的个数跟清理掉过期和删除的数据。 合并原理是,先从这些待合并的数据文件中依次读出KeyValue,再由小到大排序后写入一个新的文件。之后,这个新生成的文件就会取代之前已合…...

MySQL定期整理磁盘碎片

MySQL定期整理磁盘碎片&#xff1a;提升数据库性能的终极指南 MySQL作为一个强大的关系型数据库管理系统&#xff0c;在长时间运行后可能会产生磁盘碎片&#xff0c;影响数据库性能。本博客将深入讨论如何定期整理MySQL磁盘碎片&#xff0c;以确保数据库的高效运行。我们将介绍…...

【centos7安装docker】

背景&#xff1a; 学习docker&#xff0c;我是想做一个隔离环境&#xff0c;并且部署的话&#xff0c;希望实现自动化&#xff0c;不为安装软件而烦恼&#xff0c;保证每个人的环境一致。 2C4G内存 50G磁盘的虚拟机事先已经准备完毕。 1.查看下centos版本&#xff0c;docker要…...

四、Flask学习之JavaScript

四、Flask学习之JavaScript JavaScript&#xff0c;作为一种前端脚本语言&#xff0c;赋予网页生动的交互性和动态性。通过它&#xff0c;开发者能够操作DOM&#xff08;文档对象模型&#xff09;实现页面元素的动态改变、响应用户事件&#xff0c;并借助AJAX技术实现异步数据…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...