《我是你的妈妈呀》 * 第一期

记得我初中的时候,学校发的一个小册子的名字就是母题啥的。

大概意思是市面上的题(尤其是中考题)都是这些母题生的,都是它们的儿子。

熟悉我的朋友应该知道,我有一个风格:”喜欢用通俗易懂的语言以及图片,还原解题过程“。包括我是如何抽象的,如何与其他题目建立联系的等。比如:

如果把这个思考过程称之为自顶向下的话,那么实际上能写出来取决于你:

  • 是否有良好的抽象能力

  • 是否有足够的基础知识

  • 是否能与学过的基础知识建立联系

如果反着呢? 我先把所有抽象之后的纯粹的东西掌握,也就是母题。那么遇到新的题,我就往上套呗?这就是我在《LeetCode 题解仓库》中所说的只有熟练掌握基础的数据结构与算法,才能对复杂问题迎刃有余。 这种思路就是自底向上。(有点像动态规划?) 市面上的题那么多,但是题目类型就是那几种。甚至出题人出题的时候都是根据以前的题目变个条件,变个说法从而搞出一个“新”的题。

这个专题的目标就是从反的方向来,我们先学习和记忆底层的被抽象过的经典的题目。遇到新的题目,就往这些母题上套即可。

那让我们来自底向上看下第一期的这八道母题吧~

母题 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 为两个链表中较短的那个的长度。

  • 时间复杂度:$O(Nlogk)$,其中 N 为两个链表中较短的那个的长度

  • 空间复杂度:$O(max(logk, N))$,其中 N 为两个链表中较短的那个的长度

全家福

最后送大家一张全家福:

子题

实际子题数量有很多,这里提供几个供大家练习。一定要练习,不能眼高手低。多看我的题解,多练习,多总结,你也可以的。

总结

母题就是抽象之后的纯粹的东西。如果你掌握了母题,即使没有掌握抽象的能力,依然有可能套出来。但是随着题目做的变多,“抽象能力”也会越来越强。因为你知道这些题背后是怎么产生的。

本期给大家介绍了八道母题, 大家可以在之后的刷题过程中尝试使用母题来套模板。之后会给大家带来更多的母题。

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

最后更新于