↓快轉到主要內容

Divide-and-Conquer

LeetCode 324: Wiggle Sort II

2022-11-17·1 分鐘

LeetCode Medium Array Divide-and-Conquer Greedy Sorting

LeetCode 324 解題筆記：排序後分成小的一半和大的一半，各自反轉後交錯放：小的放偶數位置、大的放奇數位置

LeetCode 148: Sort List

2022-11-17·1 分鐘

LeetCode Medium Linked-List Two-Pointers Divide-and-Conquer Sorting

LeetCode 148 解題筆記：用快慢指針切成兩半，遞迴排序後合併；O(n log n)，不需要額外陣列

LeetCode 240: Search a 2D Matrix II

2022-11-12·1 分鐘

LeetCode Medium Array Binary-Search Divide-and-Conquer Matrix

LeetCode 240 解題筆記：從右上角開始，比目標大就往左、比目標小就往下，每一步排除一整列或一整欄

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

2022-11-10·1 分鐘

LeetCode Medium Array Hash-Table Divide-and-Conquer Tree

LeetCode 106 解題筆記：後序的最後一個是根；從後序尾巴往前取根時，要先建右子樹再建左子樹

LeetCode 973: K Closest Points to Origin

2022-10-29·1 分鐘

LeetCode Medium Array Math Divide-and-Conquer Geometry

LeetCode 973 解題筆記：跟 Top-K 一樣，用大小為 k 的 max-heap（存負的距離）保留最近的 k 個點

LeetCode 215: Kth Largest Element in an Array

2022-10-29·1 分鐘

LeetCode Medium Array Divide-and-Conquer Sorting Heap-Priority-Queue

LeetCode 215 解題筆記：維持大小為 k 的 min-heap，堆頂就是第 k 大；或用 quickselect 平均 O(n)

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

2022-10-29·2 分鐘

LeetCode Medium Array Hash-Table Divide-and-Conquer Tree

LeetCode 105 解題筆記：前序的第一個是根，在中序裡找到根的位置就知道左子樹有幾個節點；用字典查位置，O(n)

LeetCode 347: Top K Frequent Elements

2022-10-27·1 分鐘

LeetCode Medium Array Hash-Table Divide-and-Conquer Sorting

LeetCode 347 解題筆記：先計數，再用大小為 k 的 heap 或 bucket sort（次數當 index）取出次數最多的 k 個

LeetCode 169: Majority Element

2022-08-20·1 分鐘

LeetCode Easy Array Hash-Table Divide-and-Conquer Sorting

LeetCode 169 解題筆記：Boyer-Moore 投票，不同的數兩兩抵消，最後留下的就是出現超過一半的那個

LeetCode 108: Convert Sorted Array to Binary Search Tree

2022-08-16·1 分鐘

LeetCode Easy Array Divide-and-Conquer Tree Binary-Search-Tree

LeetCode 108 解題筆記：中間的元素當根，左右兩半遞迴；左右大小最多差 1，自然是平衡的