Skip to content

Latest commit

 

History

History
420 lines (317 loc) · 13.2 KB

03-双指针.md

File metadata and controls

420 lines (317 loc) · 13.2 KB
Raw

双指针

参考: 双指针技巧直接秒杀五道算法题

双指针是一种时间复杂度 O(n)，空间复杂度 O(1) 的算法

一、快慢双指针

快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题

1、寻找链表的中点

快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

  • 当链表的长度是奇数时，slow恰巧停在中点位置；
  • 如果长度是偶数，slow最终的位置是中间偏右
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

例题：876-[快慢双指针]-链表的中间结点

寻找链表中点的一个重要作用是对链表进行归并排序。「还没理解」

回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。对于链表，合并两个有序链表是很简单的，难点就在于二分。

2、环检测：Floyd判圈算法

参考 1：Cycle detection

参考 2：为什么用快慢指针找链表的环，快指针和慢指针一定会相遇？

参考 3：【证明】判断链表存在环——快慢指针一定能相遇

Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)，是一个可以在有限状态机、迭代函数或者链表上「判断是否存在环」，以及判断环的起点与长度的算法。

有下面几个结论：

  • 如果从「同一个起点」（即使这个起点不在某个环上）同时开始以「不同速度」前进的2个指针最终相遇，那么可以判定存在一个环，且可以求出2者相遇处所在的环的起点与长度。
  • 只要满足快慢指针速度差为 1，即可判断是否存在环（不一定慢1快2）
  • 如果存在环，那么在某个环上以「不同速度」前进的2个指针必定会在某个时刻相遇（即便不同起点）

应用：

循环检测的应用包括测试伪随机数生成器和密码哈希函数的质量、计算数论算法、检测计算机程序中的无限循环和元胞自动机中的周期性配置、链表数据结构的自动形状分析以及死锁检测用于 DBMS 中的事务管理

1）是否有环

例题：141-[环问题-是否有环]-环形链表

经典解法使用快慢两个指针，快指针每次走两步，慢指针每次走一步。

  • 如果不含环，快指针会先遇到 null，说明链表不含环；
  • 如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

下面的实现，不会错过起点为环入口

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

同一地点出发，不同速度的指针也可以检测环，slow=2、fast=3

slow=1、fast=3 在141题的 OJ 中测试也行

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next && fast->next->next) {
            fast = fast->next->next->next;
            slow = slow->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

当然还有种空间复杂度为 O(n) 的解法，走过的放入集合

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        s = set()
        for n in nums:
            if n not in s:
                s.add(n)
            else:
                return True
        return False

2）若有环，求环的起点

例题：142-[环问题-环入口]-环形链表

当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同的速度前进，再次相遇时所在的节点位置就是环开始的位置

下面的算法实现：

  • 第一步找到慢指针 slow 和快指针 fast 在环内的相遇点
  • 第二步将快指针重新指向head，fast 与 slow 以每次走一步的速度往前走

最后相遇的位置就是环的起始位置

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        bool isLoop = false;
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) {
                isLoop = true;
                break;
            }
        }
        if (!isLoop) return NULL;

        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

3）环的长度

快指针不动，慢指针开始走动，记录走的距离，当遇到快指针的时候就得到环的长度

class Solution {
public:
    bool hasCycle(ListNode *head) {

        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) break;
        }
        int length = 1;
        slow = slow->next;
        while (slow != fast) {
            slow = slow->next;
            length++;
        }
        return length;
    }
};

4）证明

证明 1：慢指针速度为 1、快指针速度为 2 一定能相遇

数学归纳法

首先，由于链表是个环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程。那么做如下思考：

  1. 快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。

  2. 快指针与慢指针之间差两步。此时唏嘘往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。

  3. 快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差 N-1步。转化为上一种情况。

因此此题得证。若存在环，快指针必然与慢指针相遇。

证明 2：不同速度的快慢指针是否能相遇

数学证明—线性同余等式（没看懂）

结论是可以相遇，但要满足快慢指针速度差为 1，即可判断链表存在环

证明 3：寻找环起点的算法

我们先设置慢指针 slow 和快指针 fast ，慢指针每次走一步，快指针每次走两步，根据「Floyd 判圈算法」两个指针在有环的情况下一定会相遇，此时我们再将 finder 放置起点 0，slow 和 finder 两个指针每次同时移动一步，相遇的点就是答案。（当然也可以将 fast 重新指向 0，再与 slow 同时走）

假设环长为 L，从起点到环的入口的步数是 a，从环的入口继续走 b 步到达相遇位置，从相遇位置继续走 c 步回到环的入口，则有 L=b+c ，其中 L、a、b、c 都是正整数。根据上述定义，慢指针走了 a+b 步，快指针走了 2(a+b) 步。从另一个角度考虑，在相遇位置，快指针比慢指针多走了若干圈，因此快指针走的步数还可以表示成 a+b+kL，其中 k 表示快指针比慢指针在环上多走的圈数。联立等式，可以得到 $$ 2(a + b) = a + b + kL $$

因为 L=b+c，所以 $$ \begin{aligned} a &= -b + kL \ &= c + (1-k)L \end{aligned} $$ 从上述等式可知：

  • 「查找指针」从起点出发，「慢指针」从相遇位置同时出发，每次两个指针都移动一步
  • 「查找指针」走了a 步之后到达环的入口，「慢指针」在环里从相遇位置走了 c 步和 k−1 圈到环的入口
  • 最终「查找指针」和「慢指针」在环的入口相遇，相遇点就是答案

二、前后双指针

1、寻找链表的倒数第 n 个元素

使用前后双指针，前面的指针先走 n 步，后面的指针开始同速前进。这样当前面的指针走到链表末尾null时，后面的指针所在的位置就是倒数第n个链表节点

具体实现上，需要先建个哨兵头节点，可以防止很多异常用例。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* hair = new ListNode(0, head);
        ListNode* front = head;
        ListNode* back = hair;
        for (int i = 0; i < n; i++) {
            front = front->next;
        }  // 此时 front 与 back 之间距离为 n + 2
        while (front != nullptr) {
            front = front->next;
            back = back->next;
        }
        // 此时 front 为原链表后的 null，back 指向删除节点的前一个
        back->next = back->next->next;
        return hair->next;
    }
};

例题：19-[栈-前后双指针]-删除链表的倒数第N个结点

2、数据有序，相同元素最多保留 k 位 问题

  • 对于前 k 个数字，直接保留
  • 对于 k 个后面的数字，与当前写入的位置，从后往前数的第 k 个元素进行比较，不相同则保留

此方法的正确性根源为：「数据有序」

例题：26-80-[数据有序-相同元素最多保留k位]-删除数组中的重复项

三、左右双指针

左右指针在数组中实际是指两个索引值，一般初始化为left = 0, right = nums.length - 1

一般情况下要求原始数组是有序的，但是无序的数组也可应用

1、二分

二分算法其实就是左右双指针

2、两数之和

在有序数组中，left = 0 指向最小的值，right = n - 1，指向最大的值

  • 如果当前值比 target 小，left++
  • 如果当前值比 taget 大，right--
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;
        while (left < right) {
            int tmp = numbers[left] + numbers[right];
            if (tmp == target) {
                return {left, right};
            } else if (tmp < target) {
                left++;
            } else if (tmp > target) {
                right--;
            }
        }
        return {};
    }
};

例题：167-[左右双指针-入门]-两数之和II

3、反转数组

  • 如果数组长度为奇数，最后跳出循环时 left == right，不用交换
  • 如果数组长度为偶数，最后跳出循环时 left > right，不用交换
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

例题：344. 反转字符串

4、滑动窗口

滑动窗口也是双指针

  • 窗口右边的指针 right 控制元素进入窗口
  • 窗口左边的指针 left 控制元素出窗口

四、指向各自集合的双指针

算法步骤：

  • 将所有集合排序，进行数据预处理
  • 每个集合有自己的指针，并指向开头
  • 循环条件为：所有的指针都在数据长度的范围内
  • 在循环内部，指针指向元素的消耗，引起指针往后移动（要消耗的写在 if 里）

模版：

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 尽量小的饼干，刚好满足胃口小的小孩
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int ans = 0;
        int ptr1 = 0, ptr2 = 0;  // ptr1指向小孩，ptr2指向饼干
        while (ptr1 < g.size() && ptr2 < s.size()) {
            // cout << ptr1 << " " << ptr2 << endl;
            if (s[ptr2] >= g[ptr1]) { // 将必须要消耗的写在 if 里，并计数
                ans++;
                ptr1++;  // 消耗掉一个小孩，往后指一位
            }
            ptr2++;  // 消耗掉一个饼干，或当前饼干小了，都往后指
        }
        return ans;
    }
};

另一种情况

int i = s.length() - 1;
int j = t.length() - 1;

while (true) {
    while (i >= 0) {
        if (找到想要的值) {
            break;
        } else {
            i--;
        }
    }
    // 此时 i 指向 s 中想要的值
    while (j >= 0) {
        if (找到想要的值) {
            break;
        } else {
            j--;
        }
    }
    // 此时 j 指向 t 中想要的值
    if (i >= 0 && j >= 0) {  // 都大于等于0
        if (s[i] != t[j]) {
            return false;
        }
    } else {                       // 其中一个小于零 或 都小于零
        if (i == -1 && j == -1) {  // 同时到达 -1 时，返回 True
            return true;
        } else {
            return false;
        }
    }
    i--, j--;
}
return true;  // 逻辑不会走到这里