做外贸比较好的网站,莱芜信息港房产网,wordpress页面音乐播放器,信用惠州网站建设什么是双指针算法
双指针是指在遍历元素时#xff0c;不是使用单个指针进行遍历而是使用两个指针进行访问#xff0c;从而达到相应目的#xff1b;注意这个指针不是c语言中那个指向地址的指针#xff1b;
双指针分类
双指针分为对撞指针和快慢指针#xff1b;
对撞指针…什么是双指针算法
双指针是指在遍历元素时不是使用单个指针进行遍历而是使用两个指针进行访问从而达到相应目的注意这个指针不是c语言中那个指向地址的指针
双指针分类
双指针分为对撞指针和快慢指针
对撞指针两个指针方向相反例如你需要用两个指针去遍历一个数组一个从数组起始点开始进行遍历一个指针是从最后开始遍历
快慢指针快慢指针是方向相同例如一个数组都是从数组起始的地方进行遍历或者都是从尾部进行遍历快慢指针又称为弗洛伊德算法兔子乌龟算法
快慢指针常用判别链表中是否有环
接下来用题目详细介绍这两种算法
对撞指针
对撞指针常用于解决那些问题
有序数组两数之和
二分查找
三数之和(无序
最接近的三数之和
有序数组两数之和
例题链接. - 力扣LeetCode
题目描述
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例
输入numbers [2,7,11,15], target 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。
先上代码
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int i0;int jnumbers.size()-1;while(ij){int sumnumbers[i]numbers[j];if(sumtarget)i;else if(sumtarget)j--;elsereturn vectorint{i1,j1};}return vectorint{-1,-1};}
};
解释一下这段代码就是题目已经告诉我们按非递减顺序排好了那就说明数组已经按照递增顺序排好了接下来就是按照要求求和这个数组右边是最大值左边是最小值那就设两个指针进行遍历在这段代码中设的就是i和j分别给i和j赋值在这里,numbers[i]就是这个数组的最小值numbers[j]就是这个数组的最大值然后相加将相加的值与目标值进行比较如果小于目标值说明需要将值增大就要将i向右移因为右边的值大于左边的值如果大于同理就要让这个值小一点所以r向左移如果相等说明找到了就返回
三数之和(无序)
有人会疑惑三数之和双指针怎么去满足看看下面的题去解释
题目三数之和
题目链接. - 力扣LeetCode
题意
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。
先看代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {int nnums.size();sort(nums.begin(),nums.end());vectorvectorint ans;for(int first0;firstn;first){if(first0nums[first]nums[first-1])continue;int thirdn-1;int target-nums[first];for(int secondfirst1;secondn;second){if(secondfirst1nums[second]nums[second-1])continue;while(secondthirdnums[second]nums[third]target){third--;}if(secondthird)break;if(nums[second]nums[third]target)ans.push_back({nums[first],nums[second],nums[third]});}}return ans;}
};
在此解释一下这段代码先将数组进行排序排完之后在设置一个vector的容器然后就是三层循环最主要的是那两个for循环第一个for循环循环first的指向将first不断向前移动这里面的双指针分别是second和third,third赋值为n-1就是将third置为数组的最右边将目标值减去nums[first]的值那么目标值就是second和third值之和然后开始进行移动两个指针如果值大于目标1值说明需要third的值向左移因为左边的值要小往左移移到second等于third说明所有的值都大于目标值那直接就退出最里面的for循环说明在移second也没有用了因为second的值是往右移的值一直增大后面的值会更大于目标值target找到符合的值就假如到ans容器中到最后进行返回 二分查找
二分查找就不再举例子了因为二分查找中本来就蕴含了双指针的思想他本来就设两个指针一边是在数组的最左边一个指针指向数组最右边所以不再说了这属于二分算法中的一环了
快慢指针
快慢指针有龟兔赛跑的名字非常的亲切
快慢指针运用的领域
快慢指针可以利用在链表中也可以运用在数组中
运用在链表中有以下几种运用的方式
1.判断环形链表
2.找出倒数第k个结点
3.找出链表中间结点
4.找到环形链表的的入口进阶
5. 相交链表
1.判断环形链表
题目链接. - 力扣LeetCode
题意
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
示例1
输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {if(headNULL||head-nextNULL)return false;struct ListNode *slowhead,*fasthead-next;while(slow!fast){if(fast-nextNULL||fast-next-nextNULL){return false;}fastfast-next-next;slowslow-next;}return true;
}
判断环形链表是快慢指针的典型题目在有环链表如果它有环快指针每次走两步慢指针每次走一步那么有环他们必定相遇注意一定要是快指针走两步慢指针每次走一步如果走别的步数可能就不能去辨别了为什么呢这里涉及到数学问题了原来计算机的尽头真的是数学啊
走一步那么快指针比慢指针每次多走一步是1的倍数那么如何它们都会相遇
如果快指针每次走三步那么快指针每次比慢指针走2步那么就不是1的倍数了而一个奇数无论减几个偶数它都是奇数它们就不会相遇同样偶数也是如此所以快慢指针中慢指针走一步而快指针走两步是最好的结果
2.找出倒数第k个结点
题目链接https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/
题意给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号请查找并返回倒数第 cnt 个训练项目编号。
示例1
输入head [2,4,7,8], cnt 1
输出8
代码 ListNode* trainingPlan(ListNode* head, int cnt) {ListNode* l,*r;lrhead;if(headNULL)return NULL;for(int i0;icnt;i)rr-next;while(r!nullptr){rr-next;ll-next;}return l;}
解释一下这段代码就是让快指针先移步k个结点(注意代码中ans就是k)然后快指针与慢指针一起移动当快指针移到空的时候慢指针到达的位置就是倒数第k个位置(倒数第ans个位置)为什么呢? 这里需要涉及相关的数学公式列方程
假如链表的长度是n那么在头指针到这个位置就是(n-k)那么当一个指针移动n-k个位置时就到达了倒数第k个位置那么快指针先移动了k个位置那它剩下的就是n-k个位置那么这时候慢指针和快指针一起移动当快指针为空的时候慢指针就到达了第k个位置了
3.找出链表中间结点
题目链接. - 力扣LeetCode
题意
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
示例
输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。
代码 ListNode* deleteMiddle(ListNode* head) {if (head-nextnullptr) { return nullptr; }ListNode* rhead;ListNode* lhead;ListNode* prenullptr;while(ll-next){ll-next;ll-next;prer;rr-next;}pre-nextpre-next-next;return head;}
解析一下这段代码这个就是快指针走两步慢指针走一步那么当快指针走完之后慢指针刚好到达中点
下面举两个例子分别分析奇数和偶数个数的情况
当数是奇数个
1-2-3-4-5
快指针和慢指针都从1开始走当快指针走到5的时候慢指针刚好到达3也就是中间位置这个时候快指针的条件就是r-nextNULL
当数的个数是偶数个时
1-2-3-4-5-6
快指针和慢指针都从1开始走当快指针走到6后面的时候慢指针刚好到达4满足条件的位置这个时候快指针的条件就是rNULL;
所以这段代码整体的意思就影刃而解了
4.找到环形链表入口
题目链接. - 力扣LeetCode
题意
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
示例
输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。
代码 ListNode *detectCycle(ListNode *head) {ListNode *slowhead,*fasthead;while(fast!nullptr){slowslow-next;if(fast-nextnullptr)return nullptr;fastfast-next-next;if(fastslow){fasthead;while(fast!slow){fastfast-next;slowslow-next;}return slow;}}return nullptr;}
在这里先解释一下这道题的原理把环形链表讲清楚 如何判断环形链表如何找到环形链表的入口 LeetCode142.环形链表II_哔哩哔哩_bilibili
这个视频解释的非常清楚不理解的可以看看因为我这里没有图就不做多的解释了本来想尝试画一下图感觉太抽象了
解释一下这段代码吧就是先看看这fast或者fast-next是不是为空因为fast一下挑两格所以有可能是fast为空也有可能fast-next为空之后就是fast一下走两步,slow每次走一步当slow和fast第一次相遇时将fast置为head在此相遇时就是入口这里还是数学公式的推导视频里很详细
5.相交链表
提名链接. - 力扣LeetCode
题意
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
自定义评测
评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案
示例1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3
输出Intersected at 8
解释相交节点的值为 8 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。
在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。
— 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。代码 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA nullptr || headB nullptr) {return nullptr;}// 计算链表 A 和链表 B 的长度int lenA 0, lenB 0;ListNode *tempA headA, *tempB headB;while (tempA ! nullptr) {lenA;tempA tempA-next;}while (tempB ! nullptr) {lenB;tempB tempB-next;}// 将指针移动到使它们的长度相等的位置上tempA headA;tempB headB;if (lenA lenB) {int diff lenA - lenB;while (diff-- 0) {tempA tempA-next;}} else {int diff lenB - lenA;while (diff-- 0) {tempB tempB-next;}}// 遍历链表直到找到交点while (tempA ! nullptr tempB ! nullptr) {if (tempA tempB) {return tempA;}tempA tempA-next;tempB tempB-next;}return nullptr; // 没有交点
}
解析一下这段代码
先通过循环求出两个链表的长度然后让比较长的那个链表先走一段距离使两个链表到最后的结点的长度是相同的然后遍历两个链表相等了就是相遇了就表示有交点否则就没有交点
题例
多说无益以题见真章
这段题目是综合进阶的题目
逛画展
题目链接逛画展 - 洛谷
题意
博览馆正在展出由世上最佳的 mm 位画家所画的图画。
游客在购买门票时必须说明两个数字aa 和 bb代表他要看展览中的第 aa 幅至第 bb 幅画包含 a,ba,b之间的所有图画而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然他想最小化购买门票的价格。
请求出他购买门票时应选择的 a,ba,b数据保证一定有解。
若存在多组解输出 aa 最小的那组。
输入格式
第一行两个整数 n,mn,m分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
第二行包含 nn 个整数 aiai代表画第 ii 幅画的名师的编号。
输出格式
一行两个整数 a,ba,b。
输入输出样例
输入
12 5
2 5 3 1 3 2 4 1 1 5 4 3输出
2 7
代码如下
#includeiostream
using namespace std;
int cnt,ans,n,m,a[1000005],b[1000005],ansl,ansr;
void I(int x)
{if(b[x]0){cnt;}b[x];
}
void D(int x)
{if(b[x]1){cnt--;}b[x]--;
}
int main()
{cinnm;for(int i1;in;i){cina[i];}ansn;for(int l1,r1;rn;r){I(a[r]);while(true){D(a[l]);if(cntm)l;else{I(a[l]);break;} }if(cntmr1-lans){ansr1-l;ansll;ansrr;}}if(ansl!0)coutansl ansr;elsecout1 ans;return 0;
}
这是一道快慢指针类型的题目
解释一下代码题目要求的是将全部画家的画包含在内并且要求包含的画最小注意它只能按照顺序去看而不能跳级去看那么就定义两个指针两个指针都指向数组的开始然后先向数组中添加一副画然后r是一直向后移动的然后就是将l这副画删除然后去判断是否满足条件如果满足条件就将l指向的这幅画删除如果不行在把这幅画添上然后就这样一直判断最后输出相应的数组其实我感觉这道题不是明确的快慢指针
在进阶
统计子矩阵
这道题是用了二维数组需要将它压缩为一维数组之后在进行指针移动
题目链接[蓝桥杯 2022 省 B] 统计子矩阵 - 洛谷
题意
给定一个 N×MN×M 的矩阵 AA请你统计有多少个子矩阵 (最小 1×11×1, 最大 N×M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK。
输入格式
第一行包含三个整数 N,MN,M 和 KK。
之后 NN 行每行包含 MM 个整数, 代表矩阵 AA。
输出格式
一个整数代表答案。
输入输出样例
输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出
19
代码如下
#includeiostream
#define int long long
using namespace std;
int a[505][505],s[505][505],ans;
int b[505];
signed main()
{int n,m,k;cinnmk;for(int i1;in;i){for(int j1;jm;j)cina[i][j];}for(int j1;jm;j){for(int i1;in;i)s[i][j]s[i-1][j]a[i][j];} //求行之间的前缀和for(int ii1;iin;ii){for(int iii;in;i){for(int j1;jm;j){b[j]s[i][j]-s[ii-1][j];}int l1,r0,sum0;while(rm){r;sumb[r];if(sumk)ans(r-l1);else{while(sumk){sum-b[l];l;}ans(r-l1);}}}}coutans;return 0;
}
解释一下这段代码算是快慢指针中的一道类型题吧
先将二维数组按列求出前缀和然后用三个嵌套循环前两个循环用于行之间的相减最后一个循环用于列之间的相减就是行之间对应进行相减就是s[1][1]-s[0][1]以此类推将它们的值加入到一个一维数组当中它这个循环就是先是第一行的值减第零行的值之后就是将第二行的值减去第零行的值.....之后第二行减第一行第三行减去第一行之后得到一个一维数组在用两个指针进行遍历第一个指针在前面如果两个位置在的数组的数相减小于k那就加上r-l1,为啥加一因为r从0开始的也就是快指针从0开始的而慢指针是从0开始的为什么是r-l注意这个数组代表的前缀和所以当这两个区间相加小于目标值那么原来这个数组它本身的值就小于目标值
双指针就先到这了自我感觉总结的并不好感觉有的知识点知道但是不知道这么说我在研究研究将它完善完善
