AJohn Blog

外观

1.4 双序列双指针

1226字约4分钟

2024-11-22

1.4.1 双指针

  1. 2540. 最小公共值

    class Solution:
def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
    p = q = 0
    while p < len(nums1) and q < len(nums2):
        if nums1[p] == nums2[q]:
            return nums1[p]
        elif nums1[p] < nums2[q]:
            p += 1
        else:
            q += 1
    return -1

    时间复杂度：O(n + m)，其中 n 为 nums1 的长度，m 为 nums2 的长度。

    空间复杂度：O(1)

  2. 88. 合并两个有序数组

    如果我们从左往右按小的插入，会覆盖元素，因为空位在后面，因此，如果我们从右往左按大的插入，会更好操作一些

    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.
    """
    i =  m - 1
    j = n - 1
    k = m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

    时间复杂度：O(n + m)，其中 n 为 nums1 的长度，m 为 nums2 的长度。

    空间复杂度：O(1)

  3. 2570. 合并两个二维数组 - 求和法

    append：所见即所得，extend：迭代地添加

    my_list = [1, 2, 3]
my_list.append([5, 6]) # 输出: [1, 2, 3, 4, [5, 6]]
    my_list = [1, 2, 3]
my_list.extend([5, 6]) # 输出: [1, 2, 3, 4, 5, 6]
    class Solution:
def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
    res = []
    p = q = 0
    while 1:
        if q == len(nums2):
            res.extend(nums1[p:])
            return res
        if p == len(nums1):
            res.extend(nums2[q:])
            return res
        if nums1[p][0] == nums2[q][0]:
            res.append([nums1[p][0], nums1[p][1] + nums2[q][1]])
            p += 1
            q += 1
        elif nums1[p][0] < nums2[q][0]:
            res.append(nums1[p])
            p += 1
        else:
            res.append(nums2[q])
            q += 1

    时间复杂度：O(n + m)，其中 n 为 nums1 的长度，m 为 nums2 的长度。

    空间复杂度：O(1)

  4. LCP 18. 早餐组合

    一个指针从左往右遍历第一个数组，另一个指针从右往左遍历第二个数组

    class Solution:
def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
    res = 0
    staple.sort()
    drinks.sort()
    p = 0
    q = len(drinks) - 1
    while p < len(staple):
        if staple[p] + drinks[q] > x and q >= 0:
            q -= 1
        else:
            res = res + q + 1
            p += 1
    return res % 1000000007

    时间复杂度：O(nlogn + mlogm + n + m) = O(nlogn + mlogm)，其中 n 为 staple 的长度，m 为 drinks 的长度。

    空间复杂度：O(1)

  5. 1385. 两个数组间的距离值

    枚举法

    class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    res = 0
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            if abs(arr1[i] - arr2[j]) <= d:
                res -= 1
                break
        res += 1
    return res

    时间复杂度：O(n * m)

    空间复杂度：O(1)

    双指针法

    class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    arr1.sort()
    arr2.sort()
    left ,right, res = 0, 0, 0
    for num in arr1:
        while left < len(arr2) and arr2[left] + d < num:
            left += 1
        while right < len(arr2) and arr2[right] - d <= num:
            right += 1
        if left == right:
            res += 1
    return res

    时间复杂度：O(nlogn)

    空间复杂度：O(1)

  6. 1855. 下标对中的最大距离

    class Solution:
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
    res = 0
    j = 0
    for i in range(len(nums1)):
        while j < len(nums2) and nums1[i] <= nums2[j]:
            j += 1
        res = max(res, j - i - 1)
    return res

    时间复杂度：O(n)

    空间复杂度：O(1)

  7. 925. 长按键入

    class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
    i = 0
    j = 0
    while j < len(typed):
        if i <len(name) and name[i] == typed[j]:
            i += 1
            j += 1
        elif j > 0 and name[i - 1] == typed[j]:
            j += 1
        else:
            return False
    return i == len(name)

    时间复杂度：O(n)

    空间复杂度：O(1)

1.4.2 判断子序列

提示

阿囧说：外层遍历长串，好的情况可以是没遍历完就找到了，最坏情况遍历完才知道不符合

  1. 392. 判断子序列

    class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
    if s == "":
        return True
    i = 0
    for j in range(len(t)):
        if s[i] == t[j]:
            i += 1
            if i == len(s):
                return True
    return False

    时间复杂度：O(m)，其中 m 是 t 的长度。代码只有一个循环，至多循环 O(m) 次。

    空间复杂度：O(1)

  2. 524. 通过删除字母匹配到字典里最长单词

    class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
    res = ""
    for dic in dictionary:
        dic_left = 0
        for c in s:
            if c == dic[dic_left]:
                dic_left += 1
                if dic_left == len(dic):
                    if len(dic) > len(res) or (len(dic) == len(res) and dic < res):
                        res = dic
                    break
    return res

    时间复杂度：O(n * m)

    空间复杂度：O(1)

  3. 2486. 追加字符以获得子序列

    class Solution:
def appendCharacters(self, s: str, t: str) -> int:
    t_left = 0
    for s_c in s:
        if s_c == t[t_left]:
            t_left += 1
            if t_left == len(t):
                return 0
    return len(t) - t_left

    时间复杂度：O(n)

    空间复杂度：O(1)

  4. 2825. 循环增长使字符串子序列等于另一个字符串

    class Solution:
def canMakeSubsequence(self, str1: str, str2: str) -> bool:
    str2_left = 0
    for c in str1:
        if c == str2[str2_left] or (ord(str2[str2_left]) - ord(c) + 26) % 26 == 1:
            str2_left += 1
            if str2_left == len(str2):
                return True
    return False

    时间复杂度：O(n)

    空间复杂度：O(1)

Copyright © 2024 AJohn