leetcode双指针问题总结 Python

目录

1. 二分查找

2. 有序数组中寻找两个数和等于某数

3. 两数平方和

4. 翻转字符串中的元音字符

5. 判断是否为回文字符串（最多可以删除一个字符）

6. 归并两个有序数组

7. 判断链表是否有环

8. 最长子序列

---

1. 二分查找

从有序数组 nums 中查找等于 v 的索引

示例：

输入：nums=[1,3,6,8,9], v=3

输出：1

二分查找表面上非常简单，但是实际编程还是有几个点需要注意，否则极易出现 bug。如果我们处理的是连续数值，那就容易的多，但本题目是离散整数值，所以需要注意当左指针 left 与右指针 right 相差仅仅为 1 时的处理，处理办法就是分别在左值和右值上加一和减一。

def fun(nums, v):
    left = 0
    right = len(nums) - 1
    while left <= right:          # 注意加入等号
        mid = (left + right) // 2
        if nums[mid] > v: 
            right = mid - 1       # 注意需要 -1
        elif nums[mid] < v:
            left = mid + 1        # 注意需要 +1
        else:
            return mid
    return None

2. 有序数组中寻找两个数和等于某数

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列 ?，请你从数组中找出满足相加之和等于目标数 target 的两个数。你可以假设每个输入只对应唯一的答案 ，而且你不可以 重复使用相同的元素。

示例：

输入：numbers = [2,7,11,15], target = 9

输出：[1,2]? ?解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2]?

def twoSum(numbers, target):
    low, high = 0, len(numbers)-1
    while low < high:
        sum = numbers[low] + numbers[high]
        if sum == target:
            return [low+1, high+1]
        if sum > target:
            high -= 1
        else:
            low += 1
    return [-1, -1]

3. 两数平方和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c

示例：

输入：c = 5

输出：true? ?解释：1 * 1 + 2 * 2 = 5

在 python 中开根号有三种方式，math.sqrt()、cmath.sqrt()、pow(,)，推荐使用最后一种的内置函数。

def judgeSquareSum(c):
    low = 0
    high = int(pow(c, 0.5))
    while low < high:
        res = pow(low, 2) + pow(high, 2)
        if res == c:
            return True
        elif res > c:
            high -= 1
        else:
            low += 1
    return False

4. 翻转字符串中的元音字符

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

示例 ：

输入：s = "hello"

输出："holle"

在 python 中字符串不支持 a,b=b,a 所以需要提前将字符串转换为 List。

def reverseVowels(s):
    left, right = 0, len(s)-1
    vowel = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
    s_list = list(s)
    while left < right:
        if s_list[left] in vowel and s_list[right] in vowel:
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left +=1
            right -= 1
        if s[left] not in vowel:
            left +=1
        if s[right] not in vowel:
            right -= 1
    return "".join(s_list)

5. 判断是否为回文字符串（最多可以删除一个字符）

给你一个字符串 s，最多可以从中删除一个字符。请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例：

输入：s = "aba"

输出：true

def validPalindrome(s):

    def check(s, low, high):
        while low < high:
            if s[low] == s[high]:
                low += 1
                high -= 1
            else:
                return False
        return True

    low = 0
    high = len(s) - 1
    while low < high:
        if s[low] == s[high]:
            low += 1
            high -= 1
        else:
            if check(s, low, high-1) or check(s, low+1, high):
                return True
            return False
    return True

6. 归并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

def merge(nums1, m, nums2, n):
    p1, p2 = m - 1, n - 1
    tail = m + n - 1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -=1
        tail -= 1
    while p1 >= 0:
        nums1[tail] = nums1[p1]
        p1 -= 1
        tail -= 1
    while p2 >= 0:
        nums1[tail] = nums2[p2]
        p2 -=1
        tail -= 1

7. 判断链表是否有环

给你一个链表的头节点 head ，判断链表中是否有环。

该问题有两个思路，第一个思路是搭建一个哈希表存储访问过的每一个 node 的地址，然后每访问一个 node，就检查一遍哈希表。第二个思路是快慢指针，如果链表有环那快慢指针一定会相遇。这两个思路都需要解决同一个问题即怎么判断两个 node 是同一个 node，leetcode 原生代码是推荐使用 == 运算法直接判断，但是这样判断只能说明两个 node 的值相等，不能保证是同一个 node，所以还是推荐使用 id() 函数比较 node 的地址。哈希表在运算时间上有优势，双指针在所用内存上有优势。

def hasCycle(head):
    if head == None:
        return False
    slow, fast = head, head
    while fast != None and fast.next != None:
        slow = slow.next
        fast = fast.next.next
        if id(fast) == id(slow):  # 原生代码是 fast == slow
            return True
    return False

8. 最长子序列

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]

输出："apple"

def findLongestWord(s, dictionary):
    def fun(s, target):
        len_s, len_target = len(s), len(target)
        p1, p2 = 0, 0
        while p1 < len_s and p2 < len_target:
            if s[p1] == target[p2]:
                p2 += 1
            p1 += 1
        return p2 == len_target

    res = ""
    for target in dictionary:
        if fun(s, target):
            if len(target) > len(res):
                res = target
            elif len(target) == len(res) and target < res:
                res = target
    return res