蓝桥杯算法竞赛系列第七章——六道力扣经典带你刷爆双指针
欢迎回到：遇见蓝桥遇见你，不负代码不负卿！
目录
【前言】
蓝桥杯基础部分还有三章就会更新结束，然后笔者就要准备期末考试咯，等到寒假会接着把蓝桥考前冲刺专栏给搞起来，那里都是干货，比这里要干的多！所以我们现在要做的是将基础知识点吃透。记住哦，早成者未必有成，晚达者未必不达！所以，加油吧少年。
一、什么是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个节点
原题链接：力扣
题目描述：
示例：
-
给定一个链表: 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;
-
}
-
}
四、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！
蓝桥基础部分大概还剩下三章的内容，笔者正在加班加点整理，由于近期快期末考试了，所以可能会影响进度，但是会挤时间更新的哦，铁汁们的支持就是我最大的动力，求求三连鸭。
文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。
原文链接：bit-runout.blog.csdn.net/article/details/121716566
- 点赞
- 收藏
- 关注作者
评论（0）