LeetCode刷题笔记双指针基础应用

编程入门行业动态更新时间:2024-10-24 17:21:07

双指针简介

双指针的用途：双指针主要用于单循环遍历线性表数据结构，两个指针指向不同的元素，从而协同完成任务（通常双指针分别指向元素比较，或者两元素联合与某一条件比较）

双指针的特点：不管数据输入是字符串、数组还是链表，使用一般方法的遍历方法时间复杂度度在O(n3)*和*O(n2)使用双指针对其进行遍历的平均时间复杂度为O(nlogn)，最好的情况下时间复杂度为O(n)

两种特殊形式的双指针

碰撞指针 Opposite directional：两个指针指向同一线性表，但是遍历方向相反，一个指针指向开头，另一个指向末尾，它们相向移动直到相遇或满足其他特殊条件为止快慢指针 Equi-directional：两个指针指向同一线性表，遍历方向相同，且两个指针起点可以相同，也可以不同形成一个滑动窗口，两个指针以不同的策略移动，直到两个指针的值相等或满足其他特殊条件为止

88 合并两个有序数组

给定两个有序数组，把两个数组合并为一个

输入是两个数组和它们分别的长度 m 和 n。其中第一个数组的长度被延长至 m + n，多出的 n 位被 0 填补。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

解析：

因为两个数组都是有序的，所以可以把两个指针分别放在两个数组的末尾，即 nums1 的 m-1 位和 nums2 的 n-1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。

因为本题是将结果全部存储在 nums1 中，所以还要一个指针指向 nums1 剩余空间的末尾，以便复制。

还需要分析输入的几种特殊情况：

nums2 为空，不管 nums1 是否为空直接返回 nums1nums1 元素为空，直接将 nums2 中元素位置不变的移入 nums1 中即可nums1 先于 nums2 遍历完，直接将 nums2 中剩余元素按顺序移入 nums1 中即可

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {# nums2 为空，不管 nums1 是否为空直接返回 nums1if(!n){return;}int tail1 = m-1, tail2 = n-1, tail = m+n-1;while(tail1>=0 && tail2>=0){if(nums1[tail1]>nums2[tail2]){nums1[tail--] = nums1[tail1--];}else{nums1[tail--] = nums2[tail2--];}}# nums1 先于 nums2 遍历完，直接将 nums2 中剩余元素按顺序移入 nums1 中即可while(tail2>=0){nums1[tail--] = nums2[tail2--];}}
};

524 通过删除字母匹配到字典里最长单词

给定一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

输入一个字符串和一个字符串数组，输出一个数组中按条件要求的字符串，如果答案不止一个，返回长度最长且字母序最小的字符串。

输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”

解析：

根据题意，我们需要完成两个任务：首先找到 s 可构成字符串数组中的所有字符串；然后，我们要选出这些候选字符串中长度最长且字母序最小的。

第一个任务我们采用双指针完成，一个指针指向 s 的首元素，从左向右遍历；另一个指针指向字典中当前比较的字符串首元素，也从左向右遍历，每匹配一个元素该指针移动一步。如果全都匹配，形成一个候选字符串。

第二个任务我们可以对字典进行预处理，根据字符串长度进行排序，优先匹配较长的字符串，只要匹配成功就直接返回该字符串。

class Solution {
public:string findLongestWord(string s, vector<string>& dictionary) {// labmda表达式自定义排序sort(dictionary.begin(), dictionary.end(), [](string a, string b){// 让字母序更小的排在前面if(a.size()==b.size()) return a < b;// 让长度更长的排在前面return a.size() > b.size();});for(const auto str: dictionary){int ps = 0, pstr = 0;while(ps<s.size() && pstr<str.size()){if(s[ps]==str[pstr]){++pstr;}++ps;}if(pstr==str.size()){return str;}}return "";}
};

160 相交链表

给定两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
输入两个单链表，输出一个节点表示两链表的交点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解析：

用双指针可以简单解决本题，我们定义两个指针分别指向两个链表的头节点 pa 和 pb，他们同时出发从左向右遍历，如果遍历完当前链表就接着从另一个链表的头节点开始遍历。这种遍历方式有如下两种情况：

如果两个链表存在交点，假设 headA 到交点的节点个数为 a，headB 到交点的节点个数为 b，交点到链表尾节点的节点个数为 c。那么在遍历过程中 pa 的移动距离为 a + c + b，而 pb 的移动距离为 b + c + a，所以 pa 和 pb 最终会在交点处相遇。如果两个链表不存在交点，那么在遍历过程中 pa 的移动距离为 a + b，pb 的移动距离为 b + a，所以 pa 和 pb 最终会在两个链表结尾相等，返回 nullptr

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == nullptr || headB == nullptr){return nullptr;}ListNode *pa = headA, *pb = headB;while(pa!=pb){if(pa){pa = pa->next;}else{pa = headB;}if(pb){pb = pb->next;}else{pb = headA;}}return pa;}
};