《我是你的媽媽呀》 * 第一期 · ttttt

# 《我是你的媽媽呀》 \* 第一期 # 《我是你的媽媽呀》 - 第一期記得我初中的時候，學校發的一個小冊子的名字就是母題啥的。 ![](https://img.kancloud.cn/6d/b4/6db4b63a82a065dd3f496979a6a38066_300x300.jpg) 大概意思是市面上的題（尤其是中考題）都是這些母題生的，都是它們的兒子。熟悉我的朋友應該知道，我有一個風格：”喜歡用通俗易懂的語言以及圖片，還原解題過程“。包括我是如何抽象的，如何與其他題目建立聯系的等。比如： - [一招吃遍力扣四道題，媽媽再也不用擔心我被套路啦～](https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-6/) - [超級詳細記憶化遞歸，圖解，帶你一次攻克三道 Hard 套路題（44. 通配符匹配）](https://leetcode-cn.com/problems/wildcard-matching/solution/chao-ji-xiang-xi-ji-yi-hua-di-gui-tu-jie-dai-ni-yi/) - [穿上衣服我就不認識你了？來聊聊最長上升子序列](https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/solution/chuan-shang-yi-fu-wo-jiu-bu-ren-shi-ni-liao-lai-3/) - [扒一扒這種題的外套（343. 整數拆分）](https://leetcode-cn.com/problems/integer-break/solution/ba-yi-ba-zhe-chong-ti-de-wai-tao-343-zheng-shu-cha/) 如果把這個思考過程稱之為自頂向下的話，那么實際上能寫出來取決于你： - 是否有良好的抽象能力 - 是否有足夠的基礎知識 - 是否能與學過的基礎知識建立聯系如果反著呢? 我先把所有抽象之后的純粹的東西掌握，也就是母題。那么遇到新的題，我就往上套唄？這就是我在《LeetCode 題解倉庫》中所說的**只有熟練掌握基礎的數據結構與算法，才能對復雜問題迎刃有余。** 這種思路就是**自底向上**。（有點像動態規劃?）市面上的題那么多，但是題目類型就是那幾種。甚至出題人出題的時候都是根據以前的題目變個條件，變個說法從而搞出一個“新”的題。這個專題的目標就是從反的方向來，我們先學習和記憶底層的被抽象過的經典的題目。遇到新的題目，就往這些母題上套即可。那讓我們來自底向上看下第一期的這八道母題吧~ ## 母題 1 ### 題目描述給你兩個有序的非空數組 nums1 和 nums2，讓你從每個數組中分別挑一個，使得二者差的絕對值最小。 ### 思路 - 初始化 ans 為無限大 - 使用兩個指針，一個指針指向數組 1，一個指針指向數組 2 - 比較兩個指針指向的數字的大小，并更新較小的那個的指針，使其向后移動一位。更新的過程順便計算 ans - 最后返回 ans ### 代碼 ``` <pre class="calibre18">``` 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(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 母題 2 ### 題目描述給你兩個非空數組 nums1 和 nums2，讓你從每個數組中分別挑一個，使得二者差的絕對值最小。 ### 思路數組沒有說明是有序的，可以選擇暴力。兩兩計算絕對值，返回最小的即可。代碼： ``` <pre class="calibre18">``` def f(nums1, nums2): ans = float('inf') for num1 in nums1: for num2 in nums2: ans = min(ans, abs(num1 - num2)) return ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：O(1)O(1)O(1) 由于暴力的時間復雜度是 O(N2)O(N^2)O(N2)，因此其實也可以先排序將問題轉換為母題 1，然后用母題 1 的解法求解。 **復雜度分析** - 時間復雜度：O(NlogN)O(NlogN)O(NlogN) - 空間復雜度：O(1)O(1)O(1) ## 母題 3 ### 題目描述給你 k 個有序的非空數組，讓你從每個數組中分別挑一個，使得二者差的絕對值最小。 ### 思路繼續使用母題 1 的思路，使用 k 個指針即可。 **復雜度分析** - 時間復雜度：O(klogM)O(klogM)O(klogM)，其中 M 為 k 個非空數組的長度的最小值。 - 空間復雜度：O(1)O(1)O(1) 我們也可以使用堆來處理，代碼更簡單，邏輯更清晰。這里我們使用小頂堆，作用就是選出最小值。 ### 代碼 ``` <pre class="calibre18">``` 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)O(k)O(k)。 while 循環會執行 M 次，其中 M 為 k 個非空數組的長度的最小值。heappop 和 heappush 的時間復雜度都是 logk。因此 while 循環總的時間復雜度為 O(Mlogk)O(Mlogk)O(Mlogk)。 - 時間復雜度：O(max(Mlogk,k))O(max(Mlogk, k))O(max(Mlogk,k))，其中 M 為 k 個非空數組的長度的最小值。 - 空間復雜度：O(k)O(k)O(k) ## 母題 4 ### 題目描述給你 k 個非空數組，讓你從每個數組中分別挑一個，使得二者差的絕對值最小。 ### 思路先排序，然后轉換為母題 3 ## 母題 5 ### 題目描述給你兩個有序的非空數組 nums1 和 nums2，讓你將兩個數組合并，使得新的數組有序。 LeetCode 地址： <https://leetcode-cn.com/problems/merge-sorted-array/> ### 思路和母題 1 類似。 ### 代碼 ``` <pre class="calibre18">``` 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(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 母題 6 ### 題目描述給你 k 個有序的非空數組 nums1 和 nums2，讓你將 k 個數組合并，使得新的數組有序。 ### 思路和母題 5 類似。只不過不是兩個，而是多個。我們繼續套用堆的思路。 ### 代碼 ``` <pre class="calibre18">``` 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)O(N)O(N)。 heappop 的時間復雜度為 O(logN)O(logN)O(logN)。 - 時間復雜度：O(NlogN)O(NlogN)O(NlogN)，其中 N 是矩陣中的數字總數。 - 空間復雜度：O(N)O(N)O(N)，其中 N 是矩陣中的數字總數。 ## 母題 7 ### 題目描述給你兩個有序的鏈表 root1 和 root2，讓你將兩個鏈表合并，使得新的鏈表有序。 LeetCode 地址：<https://leetcode-cn.com/problems/merge-two-sorted-lists/> ### 思路和母題 5 類似。不同的地方在于數據結構從數組變成了鏈表，我們只需要注意鏈表的操作即可。這里我使用了迭代和遞歸兩種方式。 > 大家可以把母題 5 使用遞歸寫一下。 ### 代碼 ``` <pre class="calibre18">``` # 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)O(N)O(N)，其中 N 為兩個鏈表中較短的那個的長度。 - 空間復雜度：O(N)O(N)O(N)，其中 N 為兩個鏈表中較短的那個的長度。 ``` <pre class="calibre18">``` # 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)O(N)O(N)，其中 N 為兩個鏈表中較短的那個的長度。 - 空間復雜度：O(1)O(1)O(1) ## 母題 8 ### 題目描述給你 k 個有序的鏈表，讓你將 k 個鏈表合并，使得新的鏈表有序。 LeetCode 地址：<https://leetcode-cn.com/problems/merge-k-sorted-lists/> ### 思路和母題 7 類似，我們使用遞歸可以輕松解決。其實本質上就是 ### 代碼 ``` <pre class="calibre18">``` # 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)O(N)O(N)，其中 N 為兩個鏈表中較短的那個的長度。 - 時間復雜度：O(k?N)O(k \* N)O(k?N)，其中 N 為兩個鏈表中較短的那個的長度 - 空間復雜度：O(max(k,N))O(max(k, N))O(max(k,N)) ``` <pre class="calibre18">``` # 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)O(N)O(N)，其中 N 為兩個鏈表中較短的那個的長度。 - 時間復雜度：O(Nlogk)O(Nlogk)O(Nlogk)，其中 N 為兩個鏈表中較短的那個的長度 - 空間復雜度：O(max(logk,N))O(max(logk, N))O(max(logk,N))，其中 N 為兩個鏈表中較短的那個的長度 ## 全家福最后送大家一張全家福： ![](https://img.kancloud.cn/1c/5d/1c5ddf0317b1797120c9a404f208fe80_1514x1080.jpg) ## 子題實際子題數量有很多，這里提供幾個供大家練習。一定要練習，不能眼高手低。多看我的題解，多練習，多總結，你也可以的。 - [面試題 17.14. 最小 K 個數](https://leetcode-cn.com/problems/smallest-k-lcci/) - [1200. 最小絕對差](https://leetcode-cn.com/problems/minimum-absolute-difference/) - [632. 最小區間](https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/) - 兩數和，三數和，四數和。。。 k 數和 ## 總結母題就是**抽象之后的純粹的東西**。如果你掌握了母題，即使沒有掌握抽象的能力，依然有可能套出來。但是隨著題目做的變多，“抽象能力”也會越來越強。因為你知道這些題背后是怎么產生的。本期給大家介紹了八道母題，大家可以在之后的刷題過程中嘗試使用母題來套模板。之后會給大家帶來更多的母題。大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)