双指针

2019-07-18 本文已影响0人霍尔元件

双指针问题总结

双指针经典问题

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

双指针