歡迎回到：遇見藍橋遇見你，不負代碼不負卿！
目錄
一、什么是two pointers
二、 栗子引入
三、力扣經典
栗子一：反轉字串
栗子二：救生艇
栗子三：鏈表的中間節點
栗子四：環形鏈表
栗子五：環形鏈表 II
栗子六：鏈表的倒數第K個節點
四、藍橋結語：遇見藍橋遇見你，不負代碼不負卿！
【前言】
藍橋杯基礎部分還有三章就會更新結束，然后筆者就要準備期末考試咯，等到寒假會接著把藍橋考前沖刺專欄給搞起來，那里都是干貨，比這里要干的多！所以我們現在要做的是將基礎知識點吃透，記住哦，早成者未必有成，晚達者未必不達！所以，加油吧少年，
一、什么是two pointers
雙指標是演算法編程中一種非常重要的思想，但是很少會有教材單獨拿出來講，其中一個原因是它更傾向于一種編程技巧，而長得不太像一個”演算法”的模樣，雙指標的思想十分簡潔，但是卻提供了非常高的演算法效率，
雙指標分為三種：
普通的指標：多是兩個指標往同一個方向移動；
對撞的指標（多用于有序的情況）：兩個指標面對面移動（比如一頭一尾往中間移動）；
快慢的指標：慢指標+快指標，
注意：題目中大都是對撞指標和快慢指標，不過鐵汁不要擔心，后面有大量的經典題足以讓你牢牢掌握two pointers！
二、 栗子引入
題目：給定一個有序陣列（陣列是遞增的），如陣列arr = {1,4,5,7,9}；找兩個數之和為12，找到一組即可停止，
【方法一】：
很明顯，本題采用暴力求解很簡單，直接套用兩層回圈解決了，不過時間復雜度就得是O(N^2），這是非常低效的， 所以不可取！
暴力代碼：
for (i = 0; i < n; i++)
{
for (j = 1; j < n; j++)
{
if (arr[i] + arr[j] == k)
{
printf("%d %d\n", arr[i], arr[j]);
}
}
}【方法二】：
本題已經是有序的陣列了，所以我們可以采用“對撞的指標”來解決，
思路：
注意哦，本題中 i 和 j 不是無腦++，-- 的哦，有點類似于二分查找的感覺，不信你看，
代碼執行：
#include<stdio.h>
int main()
{
int arr[] = { 1,4,5,7,9 };
int sz = sizeof(arr) / sizeof(arr[0]);
int k = 12;
int i = 0;//i從頭開始
int j = sz - 1;//j從尾開始
while (i < j)
{
if (arr[i] + arr[j] < k)
{
i++;
}
else if (arr[i] + arr[j] > k)
{
j--;
}
else
{
printf("%d %d\n", arr[i], arr[j]);
break;
}
}
return 0;
}這樣的解法很簡單，稍加改變時間復雜度就控制到O(N)了，所以我們要掌握它！OK，下面上硬菜咯，全都是實打實的經典！
三、力扣經典
栗子一：反轉字串
原題鏈接：力扣
題目描述：
示例：
輸入：s = ["h","e","l","l","o"]
輸出：["o","l","l","e","h"]思路（對撞指標）：
采用“對撞的指標”，一個從頭走、一個從尾走，交換就完事了，so easy！
代碼執行：
void reverseString(char* s, int sSize){
char* left = s;//指向起始地址
char* right = s + sSize - 1;//指向末位地址
while(left < right)//當left>=right時就不需要交換了
{
char* temp = *left;
*left = *right;
*right = temp;
left++;
right--;
}
}栗子二：救生艇
原題鏈接：力扣
題目描述：
示例1：
輸入：people = [1,2], limit = 3
輸出：1
解釋：1 艘船載 (1, 2)示例2：
輸入：people = [3,2,2,1], limit = 3
輸出：3
解釋：3 艘船分別載 (1, 2), (2) 和 (3)思路（對撞指標）：
本題類似于上面那個引入栗子，也是采用“對撞指標”思想，不過本題一開始不是有序的，所以先排序，代碼采用C++撰寫，因為可以用STL，就不需要人為去特意撰寫一個排序演算法了，很是方便，
代碼執行：
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
//先排序陣列
sort(people.begin(),people.end());
int i = 0;//起始位置
int j = people.size() - 1;//末尾位置
int count = 0;
while(i <= j)
{
if(people[i]+people[j] <= limit)//i較特殊，想象特殊在哪里
{
i++;
}
j--;
count++;
}
return count;
}
};OK，前面都是“對撞的指標”，但是在實際運用當中包括筆試面試的時候常常出現的還是“快慢指標法”，不過不用擔心，后面有四題喲，來感受它的奇妙叭，
栗子三：鏈表的中間節點
原題鏈接：力扣
題目描述：
示例1：
輸入：[1,2,3,4,5]
輸出：此串列中的結點 3 (序列化形式：[3,4,5])
回傳的結點值為 3 ， (測評系統對該結點序列化表述是 [3,4,5])，
注意，我們回傳了一個 ListNode 型別的物件 ans，這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例2：
輸入：[1,2,3,4,5,6]
輸出：此串列中的結點 4 (序列化形式：[4,5,6])
由于該串列有兩個中間結點，值分別為 3 和 4，我們回傳第二個結點，
思路（快慢指標）：
本題采用“快慢指標”解決，慢指標一次走一步，快指標一次走兩步，不過需要注意的是本題受到節點總數是奇偶的影響，當節點總數是奇數時，fast->next == NULL，slow就指向了中間結點；當節點總數是偶數時，fast == NULL，slow就指向了中間結點，所以回圈條件有兩個，但是回圈條件的先后順序也是有講究的，不信你看代碼，
代碼執行：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
//兩個指標的起始位置都是從頭開始
struct ListNode* slow = head;
struct ListNode* fast = head;
//注意回圈條件不能寫成fast->next && fast這種形式，原因在于fast走兩步后可能就指向空了
//再執行回圈條件fast->next會導致空指標例外，越界了,但是fast寫在前面就不會出現上述情況，因為&&存在短路求值
while(fast && fast->next)
{
slow = slow->next;//slow每次走一步
fast = fast->next->next;//fast每次走兩步
}
return slow;//此時slow就指向中間節點
}栗子四：環形鏈表
原題鏈接：力扣
題目描述：
示例1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點，示例2：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環，思路（快慢指標）：
很簡單，利用快慢指標來做就行了，如果鏈表有環，那么slow和fast一定會相遇，
代碼執行：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
這里添加fast->next目的是防止空指標例外，因為回圈體內fast一次走兩步
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
return true;
}
}
return false;
}栗子五：環形鏈表 II
原題鏈接：力扣
題目描述：
示例1：
輸入：head = [3,2,0,-4], pos = 1
輸出：回傳索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點，示例2：
輸入：head = [1,2], pos = 0
輸出：回傳索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點，思路（快慢指標）：
本題比較難理解，所以筆者特意畫了出來，好好康康哦，
代碼執行：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)//先找第一次相遇點
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
break;
}
}
//鏈表無環時的情況,如果有環，一定不會有NULL
if(fast == NULL || fast->next == NULL)
{
return NULL;
}
//相遇后即有環，此時使用兩個指標，一個從頭開始走
//一個從相遇點開始走，兩者再次相遇處即為入口點
slow = head;
while(slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}栗子六：鏈表的倒數第K個節點
原題鏈接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
題目描述：
示例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.
回傳鏈表 4->5.思路（快慢指標）：
先讓fast走k步，然后fast和slow再一起走，比較簡單，這道題上次寫到過，所以直接將JAVA代碼上傳咯，
代碼執行：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
//單鏈表為空時
if(head == null) {
return null;
}
//判斷k的有效性,為了一遍遍歷鏈表解決問題，所有沒有加上k > size()這個條件
if(k <= 0) {
return null;
}
//利用快慢指標，fast先走k-1步，注意要在這里防止k>size()
ListNode fast = head;
ListNode slow = head;
while(k -1 > 0) {
if(fast.next != null) {
fast = fast.next;
k--;
}else {
return null;
}
}
//此時fast和slow一起走
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
四、藍橋結語：遇見藍橋遇見你，不負代碼不負卿！
藍橋基礎部分大概還剩下三章的內容，筆者正在加班加點整理，由于近期快期末考試了，所以可能會影響進度，但是會擠時間更新的哦，鐵汁們的支持就是我最大的動力，求求三連鴨，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/374774.html
標籤：其他
上一篇：Ubuntu 支持小米四足機器人“鐵蛋”；GitHub 首席運營官離職；JetBrains 為 Kotlin 推出跨平臺 UI 框架 | 開源日報
下一篇：Python 人臉表情識別