双指针技术

深碍√TFBOYSˉ_ 2024-04-01 11:32 82阅读 0赞

双指针技术 重要性：非常高

数据结构和算法的第2天

注意：每天都会有新的双指针技术问题和解决方案加入。
    因此，请保持每天检查这个帖子。
    
    让我们开始吧!

什么是双指针技术？

双指针是一种技术，其中使用两个指针（引用）来跟踪数组/字符串的索引。它们被精简，从而可以同时遍历数组的两个部分。

当在排序的数组中搜索配对时，这是一种有用的技术。

使用双指针技术，你可以节省空间和时间，优化你的算法。

在一个循环中，两个元素被同时访问和处理。在双指针技术中，有两种方法 -

起点和终点双指针--一个指针从起点开始，另一个指针从终点开始，直到它们相遇。

慢速和快速指针--一个慢速指针（以较慢的速度移动），另一个快速指针（移动速度是慢速指针的两倍）。

![alt][]

图片来源 Pluralsight

基于双指针技术的问题的例子 -

从排序的数组中删除重复的内容

寻找链表中的 "第N "个节点

二和二 - 输入的数组已被排序

两相和III--输入数组已被排序

反转字符串中的字II

旋转数组

有效复数

有最多水的容器

除自己之外的数组的乘积

双指针技术是如何工作的？

起点和终点指针 -> 左边和右边的指针。

一个指针从头开始，另一个指针从尾开始，直到它们相遇。

![alt][alt 1]

慢速指针和快速指针:

一个慢速运行器（以较慢的速度移动），另一个快速运行器（移动速度是慢速指针的两倍）。

![alt][alt 2]

图片来源：codebus

双指针编程中的重要模式和技术问题

1.终端指针--左和右指针

在左、右指针的情况下，从第一个元素开始，每次迭代左指针的一个元素，从末端迭代右元素。评估条件并相应地增加或减少指针。

1.  左和右指针--滑动窗口

左边和右边的指针从第一个元素开始，按照要求不断滑动（即基于目标条件）。

1.  慢速和快速指针

慢速指针移动一个元素，快速指针移动两倍的速度，即从数组的第一个索引开始移动两个元素，直到它们相遇。

模式→以下问题属于双指针技术（不限于此）。

在一个链接列表的M个节点之后删除N个节点

删除一个关联列表的中间节点

从排序的数组中删除重复的内容

双和法II--输入数组被排序

反转字符串中的字数II

旋转数组

有效复数

有最多水的容器

除自己之外的数组的乘积等

最重要的问题与解决方案 注：每天都会有新的基于两个指针技术的问题和解决方案被添加。所以每天都要检查这个帖子。

黄金法则是--通过做/实施来学习

在这里，我们将看到最重要的基于双指针技术的问题。

装有大量水的容器 问题 -

给你一个长度为n的整数数组高度。有n条垂直线，其中第1条线的两个端点是（i，0）和（i，高度\[i\]）。

找出两条线，它们与x轴一起构成一个容器，使该容器中的水最多。

返回一个容器所能储存的最大水量。

例子:

输入：height = [1,8,6,2,5,4,8,3,7] 。
    输出：49

解决方案:

主要逻辑/想法 -

主要的逻辑是取两个指针左（数组的开始）和右（容器高度的结束）和一个maxarea变量来存储当前的面积。计算面积并更新maxarea的指针。

如果左指针所指向的高度小于右指针所指向的高度，则不断增加左指针/减少右指针。持续更新最大面积。

主要逻辑 实现 -

def maxArea(self, height: List[int]) -> int:
            left,right,ans = 0,len(height)-1, 0
            
            while left < right :
                ar = (right- left) * min(height[left],height[right])
                ans = max(ans,ar)
                
                if height[left] < height[right]:
                    left +=1
                else:
                    right -=1
            return ans

问题链接

类似的模式--

最小不相容性

计算符合规则的项目

破碎的计算器

从列表的末尾删除第N个节点 问题 -

给出一个链接列表的头部，从列表的末端移除第n个节点并返回其头部。

例子:

Input: head = [1,2,3,4,5], n = 2
    Output: [1,2,3,5]

解决方案 :

主要逻辑/想法 -

主要思路是--取两个指针并不断递增，直到找到目标节点之前的一个节点（左边的指针），而右边的指针将一直走到最后，以存储要删除的节点所指向的下一个节点的地址。一旦完成，将`left.next`指向`left.next.next`来删除目标节点。

主要逻辑 实现 -

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
            temp =ListNode(0,head)
            left = temp
            right = head
            
            while n>0 and right:
                right = right.next
                n -=1
                
            while right:
                left =left.next
                right = right.next
            
            left.next = left.next.next
            return temp.next

问题链接

类似的模式--

在一个关联列表的M个节点之后删除N个节点

删除关联列表中的中间节点

交换关联列表中的节点

链接列表循环 问题 -

给出头，即一个链表的头，确定该链表中是否有一个循环。

如果列表中存在一些节点，可以通过持续跟踪下一个指针再次到达，那么链接列表中就有一个循环。在内部，pos被用来表示tail的下一个指针所连接的节点的索引。注意，pos不作为一个参数传递。

如果在链表中有一个循环，返回true。否则，返回 false。

例子 1:

Input: head = [3,2,0,-4], pos = 1
    Output: true

解决方案。

主要逻辑/想法 -

主逻辑--取两个指针，一个是慢速的X速度，另一个是快速的2倍速度。从第一个节点开始遍历，将慢速指针增加一个节点，快速指针增加两个节点。如果慢速指针遇到快速指针，则返回True（即循环存在于链表中），否则返回False。

主要逻辑 实现 -

def hasCycle(self, head: Optional[ListNode]) -> bool:
            slow, fast = head, head
            
            while fast and fast.next :
                slow= slow.next 
                fast = fast.next.next 
                if slow == fast:
                    return True 
            return False

问题链接：

本文由[ mdnice ][mdnice]多平台发布

[alt]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/efdb186dbb924568b6896fc601e4b162.png
[alt 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b52f374d2efb4b3aafc9a72227d6e00c.png
[alt 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0e10d1b56c924addb6e3de0b2c83bde2.png
[mdnice]: https://mdnice.com/?platform=4