什么是同向双指针? 什么是相向双指针?
双指针的鼻祖题 —— 两数之和 Two
Sum
链表上的快慢指针算法
快速排序 & 归并排序
• 几乎所有 Two
Sum
变种 • Partition
• Quick Select • 分成两个部分 • 分成三个部分
• 一些你没听过的(但是面试会考的)排序算法
一、相向双指针模板1
1、翻转字符串
def reverse(s):
left, right = 0, len(s)-1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
2、判断回文串
def isPalindrome(s):
i, j = 0, len(s)-1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
二、同向双指针
同向双指针的问题,是指两根指针都从头出发,朝着同一个方向前进。
通常解决的问题:
- 数组去重问题 Remove duplicates in an array
- 滑动窗口问题 Window Sum
- 两数之差问题 Two Difference
- 链表中点问题 Middle of Linked List
- 带环链表问题 Linked List Cycle
1、数组去重问题
给你一个数组,要求去除重复的元素后,将不重复的元素挪到数组前段,并返回不重复的元素个数。
def deduplication(nums):
n = len(nums)
if n == 0:
return 0
nums.sort()
result = 1
for i in range(1, n):
if nums[i - 1] != nums[i]:
nums[result] = nums[i]
result += 1
return result
2、两数之差问题
同向双指针模板
nums.sort()
target = abs(target)
j = 1
for i in range(len(nums)):
while j < len(nums) and nums[j]-nums[i] < target:
j += 1
if nums[j]-nums[i] == target:
# 找到答案
给定一个整数数组,找到两个数的 差
等于目标值。index1必须小于index2。注意返回的index1和index2不是 0-based。
def twoSum7(nums, target):
# write your code here
target = abs(target)
nums2 = [(n, i) for i,n in enumerate(nums)]
nums2.sort(key=lambda x: x[0])
result = []
j = 1
for i in range(len(nums2)):
while j < len(nums2) and nums2[j][0]-nums2[i][0] < target:
j += 1
if nums2[j][0]-nums2[i][0] == target:
if i != j:
result = (nums2[i][1]+1, nums2[j][1]+1)
break
if result[0] > result[1]:
return [result[1], result[0]]
return result
3、链表中点问题
def middleNode(self, head):
# write your code here
slow, fast = head, head
while fast and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
4、带环链表
def hasCycle(self, head):
if not head:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
参考:https://www.cnblogs.com/bonelee/p/11789330.html#4417665