【经典算法】双指针(尺取法):爱,是双向奔赴,还是你追我赶?

这篇具有很好参考价值的文章主要介绍了【经典算法】双指针(尺取法):爱,是双向奔赴,还是你追我赶?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

双向指针追踪法,每日一题,算法,c++,蓝桥杯,双指针,尺取法

  • 👑专栏内容:算法学习随笔
  • ⛪个人主页:子夜的星的主页
  • 💕座右铭:日拱一卒,功不唐捐


一、前言

双指针法又称尺取法,顾名思义,在区间操作时,使用两个指针同时遍历区间,从而实现高效操作。两个指针,就像是一男一女,他们遍历区间的过程,又何尝不像是一对男女彼此追求爱情的过程呢?

接下来一起学习双指针的恋爱过程。

双向指针追踪法,每日一题,算法,c++,蓝桥杯,双指针,尺取法

二、左右指针(双向奔赴)

我渴望能见你一面,但请你记得,我不会开口见你。这不是因为我骄傲,你知道我在你面前毫无骄傲可言,而是因为,唯有你也想见我的时候,我们见面才有意义。——《越洋情书》西蒙·波伏娃

1、定义

左右指针,顾名思义,指针i与指针j,一个在左边,一个在右边。
两个指针的遍历方向相反,一个指针i从左往右,一个指针j从右往左。最终它们会在中间相会。

左右指针认为:真正的爱是双向奔赴,不论双方的差距有多大,距离有多远,只要双向奔赴,最终必将走到一起 ~

双向指针追踪法,每日一题,算法,c++,蓝桥杯,双指针,尺取法

2、回文检查

【题目描述】 给定一个长度为 n 的字符串 S。请你判断字符串S 是否回文。
【输出描述】 输入仅1行包含一个字符串S。 1 ≤ S ≤ 1 0 6 1≤ S≤10^6 1S106,保证S只包含大小写、字母。
【输出描述】 若字符串S为回文串,则输出 Y,否则输出 N
【参考样例】 输入:abcba 输出:Y

回文:正读和倒读意义相同的,称为“回文”

#include <iostream>
using namespace std;
int main()
{
    string s;   
    cin >> s;                  //(1)读取字符
    size_t n = s.size();       //(2)获取字符长度
    int i = 0; int j = n - 1;  //(3)双指针(一左一右)
    while (i < j)             
    {
        if (s[i] != s[j])  	 //(4)判断回文
        {
            cout << "N";    
            return 0;      	 //(5)结束程序
        }
        i++; j--;           //(6)移动指针
    }
    cout << "Y";
    return 0;
}

双向指针追踪法,每日一题,算法,c++,蓝桥杯,双指针,尺取法
这道题不难,有很多种方法。但是双指针是用起来最爽的。通过这道题,我们也可以大致看出来这双向奔赴的爱情大致的模样。

	int i = 0;int j =n - 1;
    while (i < j)             
    {   
        check(i, j);  //检查题目条件
        i++; j--;    //移动指针,i从头到尾,j从尾到头
    }

三、快慢指针(你追我赶)

不要追求幸福,而要幸福地追求。过程中的享受与快乐才是我们的需求。

1、定义

快慢指针,顾名思义,指针i与指针j,在同一方向,但是指针i指针j的遍历速度不一样。恰恰是因为ij的速度不同,它们之间会产生一个大小可变的滑动窗口,而这个窗口,正是它们幸福的来源。

快慢指针认为:真正的爱恰恰是你追我赶时产生的窗口期,如果没有这种不断追赶的过程,爱将会变的无趣,这个就是爱的魅力 ~

双向指针追踪法,每日一题,算法,c++,蓝桥杯,双指针,尺取法

2、美丽的区间

【题目描述】 给定一个长度为 n n n的序列 a 1 , a 2 , ⋅ ⋅ , a n a_1,a_2,··,a_n a1,a2,⋅⋅,an和一个常数 S。对于一个连续区间如果它的区间和大于或等于 S ,则称它为美丽的区间。对于一个美丽的区间,如果其区间长度越短,它就越美丽。请你从序列中找出最美丽的区间。
【输入描述】 第一行包含两个整数,S,其含义如题所述。接下来一行包含几个整数,分别表示 a 1 , a 2 , ⋅ ⋅ , a n a_1,a_2,··,a_n a1,a2,⋅⋅,an
10 ≤ N ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 4 , 1 ≤ S ≤ 1 0 8 10≤N≤10^5,1≤a_i≤10^4,1≤S≤10^8 10N105,1ai104,1S108
【输出描述】 输出共一行,包含一个整数,表示最美丽的区间的长度。若不存在任何美丽的区间,则输出 0 。
【参考样例】
输入:

5 6
1 2 3 4 5

输出:

2
#include <iostream>
#include<algorithm>
using namespace std;
int a[101000];
int main()
{
	int n, s;
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int sum = 0, ans = 1e8;
	int i = 0, j = 0;
	while (i < n)    //遍历整个列表
	{ 
		if (sum < s)   //若区间和小于s
		{
			sum += a[i]; //区间和一直加
			i++;         //i指针右移
		}
		else
		{
			ans = min(i - j, ans); //记录短的区间长度
			sum -= a[j];          //区间和减
			j++;                  //j指针右移
		}
	}
	if (ans == 1e8)         //答案不存在
		cout << 0;
	else
		cout << ans;         
	return 0;
}

双向指针追踪法,每日一题,算法,c++,蓝桥杯,双指针,尺取法

四、后记

1、当出现有序数组或者题目具有单调性(任意一个指针的增加,条件满足与否只会出现对或错这两种情况)时,应该优先想到使用左右指针来减少遍历的时间。

2、当出现前缀和、区间的时候,可以想到使用快慢指针。

注意:篇幅有限,本文只是介绍了双指针最基础的定义和最简单的题目,双指针很多题远比本文出现的题目难。大家可以点个关注,等有时间我再继续更。

📢📢📢📢📢📢
💗 你正在阅读 【子夜的星】 的 算法笔记
👍 阅读完毕,可以点点小手赞一下
🌻 发现错误,直接评论区中帮我指正吧文章来源地址https://www.toymoban.com/news/detail-817536.html

到了这里,关于【经典算法】双指针(尺取法):爱,是双向奔赴,还是你追我赶?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据仓库内容分享(十二):数仓和大数据的双向奔赴

    在 MapReduce 流行这些年之后,针对大数据集的 分布式批处理执行引擎 已经逐渐成熟。到现在(2017年)已经有比较成熟的基础设施可以在上千台机器上处理 PB 量级的数据。因此,针对这个量级的 基本数据处理问题 可以认为已经被解决,大家的注意力开始转到其他问题上: 完

    2024年02月22日
    浏览(41)
  • 低代码和纯代码:双向奔赴,共创未来ing……

    低代码开发是近年来迅速崛起的软件开发方法,让编写应用程序变得更快、更简单。有人说它是美味的膳食,让开发过程高效而满足,但也有人质疑它是垃圾食品,缺乏定制性与深度。你认为低代码到底是美味的膳食还是垃圾食品呢,来分享一下吧! 低代码译自Low-Code,而

    2024年02月04日
    浏览(37)
  • Solana 与 DePIN 的双向奔赴,会带来 DePIN 之夏吗?

    作者:LBank Labs 研究员 F.F 编译:TinTinLand 原文:https://medium.com/@lbanklabs/new-anchor-of-solana-depin-b674d04d6980 在过去的一年里,我们观察到 Solana 和 DePIN 两者都呈现出了显著的增长。 这不仅是极客科技的突然激增,更是新应用场景的渐进演变和发现。 此外,我们见证了 Solana 区块链

    2024年02月04日
    浏览(42)
  • 智谷星图赵俊:让人才和区块链产业“双向奔赴”丨对话MVP

    区块链产业需要什么样的人才?赵俊很有发言权。 赵俊是北京智谷星图科技有限公司的技术总监,也是FISCO BCOS官方认证讲师。他2017年接触区块链,随后选择人才培育领域深耕。“为区块链行业引进更多人才这件事很有价值,跟我的职业理想很接近。”赵俊说。 6年的从业经

    2024年02月13日
    浏览(64)
  • 杭电oj Simple Set Problem 双指针 尺取法 满注释版

    👨‍🏫 题目地址 输入 输出 使用快读,避免使用 Arrays.fill() 按需初始化 避免卡常 🍑 思路

    2024年02月15日
    浏览(50)
  • 【数据结构与算法】之多指针算法经典问题

    本文为 【数据结构与算法】多指针算法经典问题 相关介绍,下边将对 链表反转 (包含 迭代反转链表 、 递归反转 、 头插法反转 ), 双指针-快慢指针 (包含 寻找单向无环链表的中点 、 判断单向链表是否有环及找环入口 ), 双指针-左右指针 (包含 两数之和 、 二分查

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

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

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

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

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

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

    2024年02月15日
    浏览(40)
  • LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】

    前言 本文总结了力扣141.环形链表|以及142.环形链表||这两道有关环形链表的求解方案,去求证链表是否带环已经如何找出入环口的结点。 有关环形链表,在BAT等大厂面试中均有出现,一般是属于 中等难度 的题,需掌握 原题传送门 给你一个链表的头节点 head ,判断链表中是

    2024年02月01日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包