leetcode:双指针的妙用
套路总结
双指针是一种思想，一种技巧或一种方法，并不是什么特别具体的算法，在二分查找等算法中经常用到这个技巧。具体就是用两个变量动态存储两个或多个结点，来方便我们进行一些操作。通常用在线性的数据结构中，比如链表和数组，有时候也会用在图算法中。
快慢指针
类似于龟兔赛跑，两个链表上的指针从同一节点出发，其中一个指针前进速度是另一个指针的两倍。利用快慢指针可以用来解决某些算法问题，比如
- 计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。
- 判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。
- 判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
- 求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了
- 求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）
Leetcode:141. Linked list cycle
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head == None:
return False
jumpSinglePtr, jumpDoublePtr = head, head.next
while jumpSinglePtr != None and jumpDoublePtr != None and jumpDoublePtr.next != None:
if jumpSinglePtr == jumpDoublePtr:
return True
jumpSinglePtr = jumpSinglePtr.next
jumpDoublePtr = jumpDoublePtr.next.next
return False
碰撞指针
一般都是排好序的数组或链表，否则无序的话这两个指针的位置也没有什么意义。特别注意两个指针的循环条件在循环体中的变化，小心右指针跑到左指针左边去了。常用来解决的问题有
二分查找问题
n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
idx1, idx2, idx = 0, 0, 0
tmp = copy.deepcopy(nums1)
while idx1 < m or idx2 < n:
if idx1 >= m:
tmp[idx] = nums2[idx2]
idx += 1
idx2 += 1
elif idx2 >= n:
tmp[idx] = nums1[idx1]
idx += 1
idx1 += 1
elif nums1[idx1] < nums2[idx2]:
tmp[idx] = nums1[idx1]
idx += 1
idx1 += 1
else:
tmp[idx] = nums2[idx2]
idx += 1
idx2 += 1
for idx1 in range(0, m + n):
nums1[idx1] = tmp[idx1]
滑动窗口法
两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。
这类问题一般包括
字符串匹配问题
子数组问题
leetcode:524. longest word in dictionary
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
def isSubStr(s: str, subs: str) -> bool:
index_s, index_subs = 0, 0
while index_s < len(s) and index_subs < len(subs):
if s[index_s] == subs[index_subs]:
index_subs += 1
index_s += 1
return index_subs == len(subs)
sorted_s = sorted(dictionary, key=lambda x: len(x),reverse=True)
ans = ""
for word in sorted_s:
if isSubStr(s,word):
if len(word) > len(ans):
ans = word
elif len(word) == len(ans):
if word < ans:
ans = word
else:
break
return ans
文档信息
- 本文作者：Yang Jucai
- 本文链接：https://yangjucai.github.io//2022/03/01/leetcode/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）