算法题：八道核心母题

发布于 2023-09-29 16:40:59 字数 8805 浏览 46 评论 0

母题 1

题目描述

给你两个有序的非空数组 nums1 和 nums2，让你从每个数组中分别挑一个，使得二者差的绝对值最小。

思路

初始化 ans 为无限大
使用两个指针，一个指针指向数组 1，一个指针指向数组 2
比较两个指针指向的数字的大小，并更新较小的那个的指针，使其向后移动一位。更新的过程顺便计算 ans
最后返回 ans

代码

def f(nums1, nums2):
    i = j = 0
    ans = float('inf')
    while i < len(nums1) and j < len(nums2):
        ans = min(ans, abs(nums1[i] - nums2[j]))
        if  nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return ans

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(1)$

母题 2

题目描述

给你两个非空数组 nums1 和 nums2，让你从每个数组中分别挑一个，使得二者差的绝对值最小。

思路

数组没有说明是有序的，可以选择暴力。两两计算绝对值，返回最小的即可。

代码：

def f(nums1, nums2):
    ans = float('inf')
    for num1 in nums1:
        for num2 in nums2:
            ans = min(ans, abs(num1 - num2))
    return ans

复杂度分析

时间复杂度：$O(N ^ 2)$
空间复杂度：$O(1)$

由于暴力的时间复杂度是 $O(N^2)$，因此其实也可以先排序将问题转换为母题 1，然后用母题 1 的解法求解。

复杂度分析

时间复杂度：$O(NlogN)$
空间复杂度：$O(1)$

母题 3

题目描述

给你 k 个有序的非空数组，让你从每个数组中分别挑一个，使得二者差的绝对值最小。

思路

继续使用母题 1 的思路，使用 k 个指针即可。

复杂度分析

时间复杂度：$O(klogM)$，其中 M 为 k 个非空数组的长度的最小值。
空间复杂度：$O(1)$

我们也可以使用堆来处理，代码更简单，逻辑更清晰。这里我们使用小顶堆，作用就是选出最小值。

代码

def f(matrix):
    ans = float('inf')
    max_value = max(nums[0] for nums in matrix)
    heap = [(nums[0], i, 0) for i, nums in enumerate(nums)]
    heapq.heapify(heap)

    while True:
        min_value, row, idx = heapq.heappop(heap)
        if max_value - min_value < ans:
            ans = max_value - min_value
        if idx == len(matrix[row]) - 1:
            break
        max_value = max(max_value, matrix[row][idx + 1])
        heapq.heappush(heap, (matrix[row][idx + 1], row, idx + 1))

    return ans

复杂度分析

建堆的时间和空间复杂度为 $O(k)$。

while 循环会执行 M 次，其中 M 为 k 个非空数组的长度的最小值。heappop 和 heappush 的时间复杂度都是 logk。因此 while 循环总的时间复杂度为 $O(Mlogk)$。

时间复杂度：$O(max(Mlogk, k))$，其中 M 为 k 个非空数组的长度的最小值。
空间复杂度：$O(k)$

母题 4

题目描述

给你 k 个非空数组，让你从每个数组中分别挑一个，使得二者差的绝对值最小。

思路

先排序，然后转换为母题 3

母题 5

题目描述

给你两个有序的非空数组 nums1 和 nums2，让你将两个数组合并，使得新的数组有序。

LeetCode 地址： https://leetcode-cn.com/problems/merge-sorted-array/

思路

和母题 1 类似。

代码

def f(nums1, nums2):
    i = j = 0
    ans = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            ans.append(nums1[i])
            i += 1
        else:
            ans.append(nums2[j])
            j += 1
    if nums1:
        ans += nums2[j:]
    else:
        ans += nums1[i:]
    return ans

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(1)$

母题 6

题目描述

给你 k 个有序的非空数组 nums1 和 nums2，让你将 k 个数组合并，使得新的数组有序。

思路

和母题 5 类似。只不过不是两个，而是多个。我们继续套用堆的思路。

代码

import heapq


def f(matrix):
    ans = []
    heap = []
    for row in matrix:
        heap += row
    heapq.heapify(heap)

    while heap:
        cur = heapq.heappop(heap)
        ans.append(cur)

    return ans

复杂度分析

建堆的时间和空间复杂度为 $O(N)$。

heappop 的时间复杂度为 $O(logN)$。

时间复杂度：$O(NlogN)$，其中 N 是矩阵中的数字总数。
空间复杂度：$O(N)$，其中 N 是矩阵中的数字总数。

母题 7

题目描述

给你两个有序的链表 root1 和 root2，让你将两个链表合并，使得新的链表有序。

LeetCode 地址： https://leetcode-cn.com/problems/merge-two-sorted-lists/

思路

和母题 5 类似。不同的地方在于数据结构从数组变成了链表，我们只需要注意链表的操作即可。

这里我使用了迭代和递归两种方式。

大家可以把母题 5 使用递归写一下。

代码

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

复杂度分析

时间复杂度：$O(N)$，其中 N 为两个链表中较短的那个的长度。
空间复杂度：$O(N)$，其中 N 为两个链表中较短的那个的长度。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        ans = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = l2
                cur = cur.next
                l2 = l2.next


        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return ans.next

复杂度分析

时间复杂度：$O(N)$，其中 N 为两个链表中较短的那个的长度。
空间复杂度：$O(1)$

母题 8

题目描述

给你 k 个有序的链表，让你将 k 个链表合并，使得新的链表有序。

LeetCode 地址： https://leetcode-cn.com/problems/merge-k-sorted-lists/

思路

和母题 7 类似，我们使用递归可以轻松解决。其实本质上就是

代码

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        if len(lists) == 1: return lists[0]
        return self.mergeTwoLists(lists[0], self.mergeKLists(lists[1:]))

复杂度分析

mergeKLists 执行了 k 次，每次都执行一次 mergeTwoLists，mergeTwoLists 的时间复杂度前面已经分析过了，为 $O(N)$，其中 N 为两个链表中较短的那个的长度。

时间复杂度：$O(k * N)$，其中 N 为两个链表中较短的那个的长度
空间复杂度：$O(max(k, N))$

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        if len(lists) == 1: return lists[0]
        return self.mergeTwoLists(self.mergeKLists(lists[:len(lists) // 2]), self.mergeKLists(lists[len(lists) // 2:]))

复杂度分析

mergeKLists 执行了 logk 次，每次都执行一次 mergeTwoLists，mergeTwoLists 的时间复杂度前面已经分析过了，为 $O(N)$，其中 N 为两个链表中较短的那个的长度。