jsp项目个人网站开发,wordpress多用户模板,vr全景网站怎么做,html个人网页中文模板双指针算法是一种常用的算法技巧#xff0c;它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。
双指针并非真的用指针实现#xff0c;一般用两个变量来表示下标#xff08;在后面都用指针来表示#xff09;
双指针算法使用两个指针在数据结构上进行迭代它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。
双指针并非真的用指针实现一般用两个变量来表示下标在后面都用指针来表示
双指针算法使用两个指针在数据结构上进行迭代并根据问题的要求移动这些指针。
双指针往往也和单调性、排序联系在一起在数组的区间问题上暴力法的时间复杂度往往都是O(n^2)的但双指针利用“单调性”可以优化到On
常见的双指针模型有
1对撞指针
指的是两个指针left、right分别指向序列的第一个元素和最后一个元素
然后I指针不断递增r不断递减直到两个指针的值相撞后错开即lr或者满足其他的特殊条件为止
对撞指针一般是用来解决有序数组或者字符串问题区间问题
查找有序数组中满足某些约束条件的一组元素问题比如二分查找、数字之和等问题。
字符串反转问题反转字符串回文数等问题。
1 使用两个指针left,right.left指向序列第一个元素即left1right指向序列最后一个元素即rightn。
2 在循环体中将左右指针相向移动当满足一定条件时将左指针右移left.当满足另外一定条件时右指针左移right--
直到两指针相撞即leftright,或者满足其他要求的特殊条件时跳出循环体
例题实战 题目描述 给定一个长度为n的字符串S请你判断字符串S是否时回文 输入描述 输入仅一行包含一个字符串S 1|S|10^6,保证S只包含大小写字母 输出描述 若字符串S为会问串则输出Y否则输出N 输入输出样例 示例 1 abcba 输出Y 回文判定 对撞指针每次判断s[l]和s[r]是否相等。如果相等进一步移动否则直接判断“不是回文串” 2快慢指针
快慢指针一般比对撞指针更难想更难写。
指的是两个指针从同一侧开始遍历序列且移动的步长一个块一个慢
移动快的指针被称为快指针一动漫的指针被称为慢指针
为了方便理解我们称快指针为r,慢指针为l,这样慢指针和快指针构成的区间为[l,r]
两个指针以不同的速度不同策略移动直到快指针移动到数组尾端或者两指针相交或者满足其他特殊条件为止。
1.使用两个指针l,r.一般l指向序列的第一个元素即l1,r一般指向序列第零个元素即r0。即初始时区间[l,r][1,0]表示为空区间。
2.在循环体中将左右指针向右移动。当满足一定条件时将慢指针右移即l。当满足另外一定条件时也可能不需要满足条件将快指针右移即r保持[l,r]为合法区间
3.到指针移动到数组尾端即ln且rn或者两指针相交或者满足其他特殊条件时跳出循环
例题
给定一个长度为n的序列a1,a2,...an和一个常数S
对于一个连续区间如果它的区间和大于或等于S则称它为美丽区间
对于一个美丽区间如果区间长度越短它越美丽
请你从序列中找出最美丽的区间
输入描述
第一含包含两个整数n,S,其含义如题所述
接下来一行包含n个整数分别表示a1,a2,...an
输出描述
输出共遗憾包含一个整数表示最美丽的区间长度
若不存在任何美丽区间则输出0
