双指针问题总结
双指针经典问题
- twoSum （有序数组）
- 字符串翻转
先看一个例子：
leetcode 345. 翻转元音字母
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Input: "hello"
Output: "holle"
Example 2:
Input: "leetcode"
Output: "leotcede"
Note:
The vowels does not include the letter "y".
下面的代码给了两种写法
- 使用while循环找到需要交换的元素
- 每一次可能的操作分成三类 只用一个while循环实现
class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
vowels = "aeiouAEIOU"
vowels = set(vowels)
s = list(s)
left, right = 0, len(s) - 1
while True:
while left < right and s[left] not in vowels:
left += 1
while left < right and s[right] not in vowels:
right -= 1
if left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
else:
break
return ''.join(s)
def reverseVowels_(self, s):
vowels = "aeiouAEIOU"
vowels = set(vowels)
s = list(s)
left, right = 0, len(s) - 1
while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
if __name__ == '__main__':
test = 'leetcode'
solu = Solution()
print(solu.reverseVowels_(test))
我仔细观察 发现当前这个交换字母的问题和快排的partition非常相似
快排的代码
def quickSort(nums, first, last):
splitpoint = partition(nums, first, last)
quickSort(nums, first, splitpoint - 1)
quickSort(nums, splitpoint + 1, last)
def partition(nums, first, last):
rand = randint(first, last) # 优化，随机取标定点，以解决近乎有序的列表
nums[first], nums[rand] = nums[rand], nums[first]
pivot = nums[first]
left, right = first + 1, last
while True: # 这里使用了双路快排，以解决有大量相同值的列表
while left <= right and nums[left] < pivot:
left += 1
while right >= left and nums[right] > pivot:
right -= 1
if left > right:
break
else:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1 # 这两行代码必须有 否则程序可能死循环 测试样例 [3,2,2,2,3]
nums[first], nums[right] = nums[right], nums[first] # right处于<=v部分最后一个元素
return right
sum类问题
- two sum
- 找出两数和小于某个值的所有情况
两数和小于定值所有情况
基本框架就是twosum双指针，当前两数小于定值之后，left不变，right减小直到left的所有组合都是满足题意的解
class Solution:
def twoSum(self, nums, target):
left, right = 0, len(nums) - 1
res = []
nums.sort()
while left < right:
temp = nums[left] + nums[right]
if temp <= target:
res.extend([[nums[left], nums[i]] for i in range(left+1, right+1)])
left += 1
else:
right -= 1
return res
if __name__ == '__main__':
test = [1,2,3,4,5,6]
solu = Solution()
print(solu.twoSum(test, 5)) # [[1, 2], [1, 3], [1, 4], [2, 3]]
交换类问题
- 翻转 a.bc.def 为 def.bc.a
- 先全部翻转 在局部翻转
- partition
