网站运营频道内容建设,标志设计要素,wordpress 产品展示 插件,网站优化吧1.双指针介绍
双指针是解题时一种常见的思路#xff0c;一般有两种用法。
1#xff09;两个指针反方向#xff0c;分别从数组开头和结尾开始移动#xff0c;例如对有序数组的搜索。
2#xff09;两个指针同方向移动#xff0c;例如快慢指针#xff0c;都是从数组开头…1.双指针介绍
双指针是解题时一种常见的思路一般有两种用法。
1两个指针反方向分别从数组开头和结尾开始移动例如对有序数组的搜索。
2两个指针同方向移动例如快慢指针都是从数组开头开始遍历只是速度不一样。
除了用于数组也可以用于链表树图。 2.反向的双指针
力扣https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
因为数组是非递减的所以可以数组首尾各置一个指针若值相加大于目标值则尾指针自减若值相加小于目标值则头指针自增这样就一步步逼近了目标值。
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int i 0, j numbers.size()-1;while(ij){int t numbers[i] numbers[j];if(targett) return vectorint({i1,j1});else if(targett){i;}else{j--;}}return vectorint();}
}; 3.同向的双指针
力扣https://leetcode.cn/problems/linked-list-cycle-ii/这题有两个要点先是要判断链表中是否有环接着是找到环的入口。
判断是否有环可以用快慢指针。
两个指针同时从起点出发快指针一次两步慢指针一次一步。
如果链表中有环则快慢指针一定会相遇就像在操场上一直跑圈速度快的人一定会在某一刻比速度慢的人多跑一圈所以二人相遇了。
若是快慢指针没有相遇且快指针指向了NULL那很明显就是没有环。 确定链表有环后就是寻找环的入口了。
可以用题目中的示例来简单理解一下。
下图使用快慢指针从起点[3]出发慢指针一次一步快指针一次两步很快这两个指针会在节点[-4]相遇。
相遇后将慢指针移回链表起点[3]快慢指针都一次走一步两个指针再次相遇的节点[2]就是环的入口。 一个简单易懂的解释就是
慢指针路径起点--环的入口--快慢指针相遇的节点
快指针路径起点--环的入口--快慢指针相遇的节点--环的入口--快慢指针相遇的节点
因为快指针路径慢指针路径*2
所以【快慢指针相遇的节点--环的入口--快慢指针相遇的节点】 【 起点--环的入口--快慢指针相遇的节点】
同时减去【环的入口--快慢指针相遇的节点】
所以【快慢指针相遇的节点--环的入口】 【 起点--环的入口】
所以找到环得到入口就是将慢指针移到起点与快指针都是一次一步直到相遇相遇节点就是环的入口。 如果还是没有理解的可以直接搜索【Floyd 判圈法】找动画视频直观理解一下。 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return NULL;ListNode* slow head, *fast head;while(slow-next fast-next fast-next-next){slow slow-next;fast fast-next-next;if(slowfast){slow head;while(slow!fast){slow slow-next;fast fast-next;}return slow;}}return NULL;}
};
