c++算法之双指针

这篇具有很好参考价值的文章主要介绍了c++算法之双指针。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

双指针简介

对撞指针

求解步骤

例题 蓝桥oj1371回文判定

题目描述

输入描述

输出描述

输入输出样例

示例 1

示例 2

运行限制

快慢指针

求解步骤

例题 蓝桥oj1372美丽的区间

题目描述

输入描述

输出描述

输入输出样例

示例 1

运行限制

例题 蓝桥oj 1621挑选字串

题目描述

输入描述

输出描述

输入输出样例

示例

运行限制


双指针简介

双指针算法是一种常用的算法技巧,它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作

双指针并非真的用指针实现,一般用两个变量来表示下标(在后面都用指针来表示)

双指针算法使用两个指针在数据结构上进行迭代,并根据问题的要求移动这些指针。

双指针往往也和单调性、排序联系在一起,在数组的区间问题上,暴力法的时间复杂度往往是O(n^2)的,但双指针利用“单调性”可以优化到O(n)。

常见的双指针有:对撞指针和快慢指针

对撞指针

指的是两个指针 left、right(简写为1,r)分别指向序列第一个元素最后一个元素

然后1指针不断递增,r不断递减,直到两个指针的值相撞或错开(即1>=r),或者满足其他要求的特殊条件为止。

对撞指针一般用来解决有序数组或者字符串问题(常见于区间问题)

查找有序数组中满足某些约束条件的一组元素问题:比如二分查找数字之和等问题

字符串反转问题:反转字符串、回文数、颠倒二进制等问题。

求解步骤

1.使用两个指针left、right。left指向序列第一个元素,即:left=1,right指向序列最后一个元素,即right=n。

2.在循环体中左右指针相向移动,当满足一定条件时,将左指针右移,left++。当满足零一条件时,将右指针左移,right--

3.知道两指针相撞(即left==right),或者满足其他要求的特殊条件时,跳出循环体。

例题 蓝桥oj1371回文判定

题目描述

给定一个长度为 nn 的字符串 SS。请你判断字符串 SS 是否回文。

输入描述

输入仅 11 行包含一个字符串 SS。

1≤∣S∣≤1061≤∣S∣≤106,保证 SS 只包含大小写、字母。

输出描述

若字符串 SS 为回文串,则输出 YY,否则输出 NN。

输入输出样例

示例 1

输入

abcba

输出

Y
示例 2

输入

abcbb

输出

N

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6 + 9;
char s[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> s + 1;
	int n = strlen(s + 1);
	int l = 1, r = n;
	bool ans = true;
	while (l < r&& ans)
	{
		if (s[l] != s[r])ans = false;
		l++, r--;
	}

	cout << (ans ? "Y" : "N") << endl;

	return 0;
}

快慢指针

快慢指针一般比对撞指针更难想也更难写

指的是两个指针从同一侧开始遍历序列,且移动的步长一个快一个慢。

移动快的指针被称为快指针,移动慢的指针被称为慢指针。

为了方便理解,我们成快指针为r,慢指针为1,这样慢指针和快指针构成区间[1,r]。

两个指针以不同速度、不同策略移动,直到快指针移动到数组尾端,或者两指针相交,或老满足其他特殊条件时为止。

求解步骤

1、使用两个指针l、r。l一般指向序列的第一个元素,即:l=1,r一般指向序列第零个元素,即:r=0.即初始时区间[1,r] = [1,0]表示空区间

2、在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即l++。当满足另外一定条件时(也可能不需要满足条件),将指针右移,即r++,保持[l,r]为合法区间。

3、到指针移动到数组尾端时(即l==n且r==n),或者两指针相交,或者满足其他特殊条件时跳出循环体。

例题 蓝桥oj1372美丽的区间

题目描述

给定一个长度为 nn 的序列 a1,a2,⋯ ,ana1​,a2​,⋯,an​ 和一个常数 SS。

对于一个连续区间如果它的区间和大于或等于 SS,则称它为美丽的区间。

对于一个美丽的区间,如果其区间长度越短,它就越美丽。

请你从序列中找出最美丽的区间​。

输入描述

第一行包含两个整数 n,Sn,S,其含义如题所述。

接下来一行包含 nn 个整数,分别表示 a1,a2,⋯ ,ana1​,a2​,⋯,an​。

10≤N≤10510≤N≤105,1×ai≤1041×ai​≤104,1≤S≤1081≤S≤108。

输出描述

输出共一行,包含一个整数,表示最美丽的区间的长度。

若不存在任何美丽的区间,则输出 00。

输入输出样例

示例 1

输入

5 6
1 2 3 4 5

输出

2

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5 + 9;
int a[N], S;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, S; cin >> n >> S;

	int ans = n + 1;
	for (int i = 1; i <= n; i++)cin >> a[i];

	for (int i = 1,j = 0,sum = 0; i <= n; i++)
	{
		//考虑移动j,即j++   because i>j说明区间不合法
		while (i > j || (j + 1 <= n && sum < S))sum += a[++j];

		if (sum >= S)ans = min(ans, j - i + 1);
		sum -= a[i];
	}
	cout << (ans>n?0:ans) << endl;
	
	return 0;
}

例题 蓝桥oj 1621挑选字串

题目描述

有 n 个数,和一个整数 m。

现要从这 n 个数选出一个连续子串,要求这个字串里面至少有 k 个数要大于等于 m。

问一共能选出多少个子串(显然子串长度要大于等于 k)。

输入描述

输入第一行是 3 个整数 n、m、k。

输入第二行是 n 个整数 a1、a2、⋯、an表示序列。

2≤n≤2000,1≤k≤n2,1≤m,ai≤109  2≤n≤2000,1≤k≤2n​,1≤m,ai≤109。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

7 4 2
4 2 7 7 6 5 1

输出文章来源地址https://www.toymoban.com/news/detail-809070.html

18

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 2e5+5;
int a[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m, k; cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)cin >> a[i];
	int ans = 0;
	for (int i = 1, j = 0, count = 0; i <= n; i++)
	{
		while (i > j || (j + 1 <= n && count < k))//j在i的左边或者>=m的数量小于k
		{
			j++;
			count += (a[j] >= m);
		}
		if (count >= k)ans += (n - j + 1);
		count -= (a[i] >= m);

	}
	cout << ans << endl;
	return 0;
}

到了这里,关于c++算法之双指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法之双指针题型:

    力扣27: 移除元素 力扣题目链接 双指针分为: 快慢双指针:同一个起点,同向出发 相向双指针:从两端出发,方向相反,终会相遇 经典的双指针(快慢双指针) 代码随想录上面有动图,很清楚 思路: 力扣977: 有序数组的平方 力扣题目链接 也是双指针法(相向指针) 如

    2024年02月09日
    浏览(44)
  • 【数据结构与算法】- (带尾指针)单循环链表 - 详细实现步骤及代码(C/C++)

    前三篇文章分别介绍了 “带头结点单链表实现”、“不带头结点单链表实现”、“带头结点单循环链表实现”。 这篇文章主要介绍 带尾指针 的单循环链表以及详细的实现步骤,最后提供我自己根据理解实现带尾指针单循环链表的C语言代码 。跟着后面实现思路看下去,应该

    2024年02月16日
    浏览(38)
  • 力扣编程题算法初阶之双指针算法+代码分析

    目录   第一题:复写零 第二题:快乐数: 第三题:盛水最多的容器 第四题:有效三角形的个数   力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路: 上期介绍到双指针,这次来用双指针实际操作。第一种从前往后复写,会导致为复写的数字被覆盖,因此选择从后往

    2024年02月04日
    浏览(39)
  • 【C++】数据结构与算法:常用排序算法

    😏 ★,° :.☆( ̄▽ ̄)/$: .°★ 😏 这篇文章主要介绍常用排序算法。 学其所用,用其所学。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路🥞 排序算法是计算机科学中常见的一类算法,用于将一组数据按照特定的顺序进行排

    2024年02月14日
    浏览(46)
  • 算法修炼之路之双指针含多道leetcode 经典题目

    目录 前言  一:普通双指针 1.经典题目一  283移动0问题 分析 代码实现 2.经典题目二 1089复写0  分析 代码实现 二:解决成环类问题-快慢指针  经典例题一 202快乐数 分析  代码实现   三:左右相遇指针 经典例题一 11 盛最多水的容器 分析  代码实现    接下来的日子会顺

    2024年04月13日
    浏览(76)
  • 算法通关村第一关——链表经典问题之双指针笔记

    基本结构 1.寻找中间结点 2.寻找倒数第k个元素 3.旋转链表

    2024年02月14日
    浏览(38)
  • 【数据结构与算法C++实现】3、排序算法

    原视频为左程云的B站教学 外层循环 :n个数需要冒n-1个泡上去,剩下的一个必然是最小的。所以外层循环执行n-1轮 内层循环 :比大小,第1个泡需要比n-1次,第2个泡,比较n-2次… 选择: 每次从待排序序列中选择 最小的一个 放在已排序序列的后一个位置 原理类似于对扑克牌

    2024年02月11日
    浏览(56)
  • 算法通关村第一关——链表经典问题之双指针专题笔记

    我一直觉得双指针是一个非常好用的方法,在链表中可以使用,在数组中依然可以,很灵活。 1. 寻找中间结点         用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步, fast 一次走两步。那么当 fast 到达链表的末尾时,slow 必然位于中间。 2. 寻找倒数第K个元素 在这

    2024年02月15日
    浏览(40)
  • C++基础-介绍·数据结构·排序·算法

    C++是一门风格严谨又不失自由的开发语言,提供了完整的内存管理、支持函数式编程和面向对象编程,支持模板、多继承、多实现、重载、重写等多态特性。 优势在于目前90%的操作系统、数据库、应用基础架构、硬件嵌入式等都是使用C/C++制作的,而C++是对C的标准扩展,掌握

    2024年02月03日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包