建设企业网站地址,河北省建设工程安全生产监督管理网站,浙江省建设信息港三类人员证书查询,微信小程序开发图解案例教程D4-双指针算法-滑动窗口快慢指针快慢指针算力扣141. 环形链表思路代码力扣142. 环形链表 II思路代码滑动窗口力扣76. 最小覆盖子串思路代码力扣424. 替换后的最长重复字符思路代码快慢指针算
快慢指针算法#xff0c;多用于链表当中#xff0c;常见的如#xff1…
D4-双指针算法-滑动窗口快慢指针快慢指针算力扣141. 环形链表思路代码力扣142. 环形链表 II思路代码滑动窗口力扣76. 最小覆盖子串思路代码力扣424. 替换后的最长重复字符思路代码快慢指针算
快慢指针算法多用于链表当中常见的如快慢指针判断链表中是否含有环路快慢指针找链表中点问题
力扣141. 环形链表
题目链接141. 环形链表
思路
这是非常经典的Floyd判圈法即利用快慢指针判断链表中是否含有环路。 1、初始时slow、fast都在开头节点 2、fast一次走两步slow一次走一步 3、如果含有环路二者一定在环路中相遇反之fast先走到尾节点 代码
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *slow head, *fast head;while (fast ! nullptrfast-next ! nullptr) {//快慢指针判断条件slow slow-next;fast fast-next-next;if (slow fast) {return true;}}return false;}
};
力扣142. 环形链表 II
题目链接142. 环形链表 II
思路
本题为上一题的进阶版本我们不仅要判断是否含有环路还要判断环路的进入节点并返回。 1、所以我们第一步就是利用快慢指针利用是否会有第一次相遇判断出是否含有环路思路同上一题。 2、当相遇时二者处在环路中某一个节点现在我们要通过分析快慢指针走过的步数来进一步指定算法 1、设非环路部分链表共a个节点环路部分链表共b个节点(a,b均未知具体要看题目) 2、我们从头部出发到达环路入口节点要么直接走过去即a步要么走入环路在环路中绕行整数个圈到达。综上总步数为 anbn为绕行圈数为未知看具体链表 3、再来分析快慢指针已经走了多少步分别设为f、s步 1f2s快指针一次两步慢指针一次一步 2fsnb快慢指针都同样走过了a步快指针多比慢指针在环路中走了几圈且n为未知 所以f2nb、snb 4、在当下慢指针已经走了nb步根据上面分析再走a步就是目标节点。但是现在a是未知根据上面分析我直接从起点走a步也会到目标点。 5、综上让快指针去链表头让快慢指针同时按照一个速度出发二者相遇的时候同时走了a步即为目标点 代码
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow head, *fast head;while (fast ! nullptrfast-next ! nullptr) {//快慢指针判断条件slow slow-next;fast fast-next-next;if (slow fast) {//产生第一次相遇证明含有环路开始寻找目标点fast head;//这里算法详见上面证明while (fast ! slow) {fast fast-next;slow slow-next;}return slow;}}return nullptr;//不产生第一次相遇不含有环路}
};
滑动窗口
1、滑动窗口又名双指针法左右两个指针l,r同方向且lr用于区间搜索。 2、只要分析出滑动窗口法之后马上想到滑窗固定大板子 1、滑窗之中一定要重点统计窗口内部数据情况这个和窗口是否收缩有很大关系 2、总体思路就是先进行右边界扩张更新窗口内数据信息再根据题意判断是否左边界进行窗口收缩收缩的话一定注意更新窗口内数据信息 3、左右指针初始化为 0 -1 int left 0, right -1;for (遍历一遍数组) {// c 是将移入窗口的字符char c s[right];// 右移窗口right;// 进行窗口内数据的一系列更新... // 判断左侧窗口是否要收缩while (左指针需要移动即窗口需要收缩) {// d 是将移出窗口的字符char d s[left];// 左移窗口left;// 进行窗口内数据的一系列更新...}力扣76. 最小覆盖子串
题目链接76. 最小覆盖子串
思路
本题要求我们在s中找一个片段这个片段中必须包含t中全部出现的字母即t中出现了2个a那么目标片段必须出现2个a且要求在所有满足要求的片段之中找到最短的(根据题意答案一定唯一)这明显是区间搜索问题马上想到滑窗法立刻开始套模板 1、初始化 l0,r-1针对滑窗我们要统计滑窗内各个元素出现的个数针对t我们要统计出现了哪些元素以及出现的次数。 2、每次先右边界扩充滑窗更新滑窗内元素。 3、最重要的地方来了如何判断是否缩小滑窗(即左边界)如果当前滑窗内都为覆盖到所有目标元素那么缩小滑窗之后更是不可能覆盖。所以只有当扩充玩新元素后全覆盖到了才考虑缩小滑窗。 4、为了看是否能达到覆盖用sum记录还需要覆盖的字母总量用tmp数组动态维护需要覆盖的各个字母剩余数量。 5、根据题意当能覆盖之后我们要这个片段尽可能的短所以在缩小滑窗时候当恰好排出这个元素之后无法完全覆盖这就代表着不缩小时就是当前的满足要求的最短片段。所以我们连续缩小滑窗直到上述情况出现即可。为了让最终结果最小要动态维护一个最短片段。 代码
注意 1、字符串裁剪函数substr使用方式 假设string s “0123456789”; string sub1 s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾sub1 “56789” string sub2 s.substr(5, 3); //从下标为5开始截取长度为3位sub2 “567” 2、比如t串中只出现两个a,但窗口内出现了三个a只有前两个算有效覆盖(既在t中出现又满足出现次数)所以tmp就是用来动态维护这个事情
class Solution {
public:string minWindow(string s, string t) {int m s.size(), n t.size();//统计字符串t里面的字符信息vectorint cnt1(128, 0);//统计t中各个字母出现的次数vectorbool visit1(128, false);//看t中出现了哪些字母for (int i 0; i n; i) {cnt1[t[i]];visit1[t[i]] true;}//用来动态记录最短符合要求字串int min_l -1, min_r -1, mins 1000001;//左边界右边界长度int l 0, r -1;//窗口左右指针int sum n;//还未覆盖到的字母总数vectorint tmp(cnt1);//复制一下cnt1动态维护一下窗口内还需要覆盖的各个字母的个数vectorint cnt2(128, 0);//维护窗口内所有元素出现的次数for (int i 0; i m; i) {char tar s[i];//待扩充进来的字符r;//扩充右边界cnt2[tar];//更新窗口内元素出现次数//扩充进来的字母是有效的覆盖解释看上面的注意部分if (visit1[tar] true tmp[tar] ! 0) {sum--;//要覆盖的总数-1tmp[tar]--;//窗口内该字母还需要出现的次数-1}//开始判断是否要缩减窗口if (sum 0) {//刚刚好窗口扩展到全覆盖时候才开始动左指针找到当前状态下最小//当前窗口完全可以覆盖为了找最小我们收缩左边界直到恰好覆盖(即再缩就不可以覆盖为止)//这时候就是当前状态下最小while (sum 0) {//连续缩小char tar2 s[l];//待排除的元素if (visit1[tar2] true) {//被扔出去的字母是有效字母,反之直接扔即可(l)cnt2[tar2]--;//动态维护窗口内各字母个数有效字母被扔出去后它的新数量if (cnt2[tar2] cnt1[tar2]) {//当前窗口不能恰好覆盖目标字母这个时候就是连续缩窗口的尽头开始更新动态维护的数据sum;//窗口内待覆盖的元素1if (r - l 1 mins) {//动态维护最小子串mins r - l 1;min_l l;min_r r;}tmp[tar2];//该字母在窗口内还需出现的次数1l;//缩窗口break;//退出连续缩窗口}}l;}}}return min_l -1 ? : s.substr(min_l, min_r-min_l1);//始终未找到合适的窗口min_l-1返回空串反之按照大小裁剪目标串s}
};
力扣424. 替换后的最长重复字符
题目链接424. 替换后的最长重复字符
思路
明显的在大区间中找一个连续的小区间经过不多于k次的变化之后让其中元素都统一且这个片段要最长。区间搜索马上想滑窗上模板 1、初始化 l0 r-1 统计窗口内各个元素个数一个窗口内为了在有限的替换之后整体最长肯定是维护一个个数最多的元素把和他不同的全换下去这样才会最长也能最大程度上利用k,所以维护窗口内最大元素个数 2、r扩充窗口更新元素数量因为该字母变多了可能成为最多的个数所以也要维护窗口内最大元素个数 3、滑窗问题关键来了缩小窗口当”非最多数量元素“个数小于等于k可替换数量说明这次扩充是可以的窗口确实可以扩张不需要收缩因为题目要的就是最长反之就得收缩更新的数据同上 代码
class Solution {
public:int characterReplacement(string s, int k) {int n s.size();vectorint cnt(26, 0);//窗口各个字母个数int l 0, r -1;int maxs 0;for (int i 0; i n; i) {char tar s[i];//待扩充元素r;//扩充cnt[tar - A];//两次更新数据maxs max(maxs, cnt[tar - A]);if (r - l 1 - maxs k) {//扩充失败了必须要收缩一下char tmp s[l];cnt[tmp - A]--;for (int j 0; j 26; j) {maxs max(maxs, cnt[j]);}l;}}return r - l 1;}
};
