引言 分治（Divide and Conquer）是一种重要的算法设计范式，它通过将复杂问题分解为更小的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。本文将深入探讨分治算法的基本原理、应用场景以及在 LeetCode 上的实际应用。
1. 分治算法的基本原理 分治算法的基本步骤包括：
分解 （Divide）：将原问题分解为若干个规模较小的子问题。解决 （Conquer）：递归地解决这些子问题。合并 （Combine）：将这些子问题的解合并成原问题的解。
2. 分治算法的基本框架 1 2 3 4 5 6 7 def divide_and_conquer (problem ): if problem is small enough: return solve_directly(problem) else : subproblems = divide(problem) subresults = [divide_and_conquer(subproblem) for subproblem in subproblems] return combine(subresults)
3. LeetCode 实战应用 3.1 LeetCode 53. Maximum Subarray 这个问题可以用分治方法解决，我们可以将数组分成左右两半，然后分别求解左半部分和右半部分的最大子数组和，以及跨越中点的最大子数组和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution : def maxSubArray (self, nums: List [int ] ) -> int : def divide_and_conquer (left, right ): if left == right: return nums[left] mid = (left + right) // 2 left_sum = divide_and_conquer(left, mid) right_sum = divide_and_conquer(mid + 1 , right) cross_sum = nums[mid] left_cross = 0 right_cross = 0 temp = 0 for i in range (mid - 1 , left - 1 , -1 ): temp += nums[i] left_cross = max (left_cross, temp) temp = 0 for i in range (mid + 1 , right + 1 ): temp += nums[i] right_cross = max (right_cross, temp) cross_sum += left_cross + right_cross return max (left_sum, right_sum, cross_sum) return divide_and_conquer(0 , len (nums) - 1 )
3.2 LeetCode 215. Kth Largest Element in an Array 这个问题可以使用快速选择算法，这是一种分治的变体。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution : def findKthLargest (self, nums: List [int ], k: int ) -> int : def partition (left, right, pivot_index ): pivot = nums[pivot_index] nums[pivot_index], nums[right] = nums[right], nums[pivot_index] store_index = left for i in range (left, right): if nums[i] < pivot: nums[store_index], nums[i] = nums[i], nums[store_index] store_index += 1 nums[right], nums[store_index] = nums[store_index], nums[right] return store_index def select (left, right, k_smallest ): if left == right: return nums[left] pivot_index = random.randint(left, right) pivot_index = partition(left, right, pivot_index) if k_smallest == pivot_index: return nums[k_smallest] elif k_smallest < pivot_index: return select(left, pivot_index - 1 , k_smallest) else : return select(pivot_index + 1 , right, k_smallest) return select(0 , len (nums) - 1 , len (nums) - k)
3.3 LeetCode 23. Merge k Sorted Lists 这个问题可以使用分治方法，将 k 个链表分成两半，递归地合并，最后合并两个有序链表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution : def mergeKLists (self, lists: List [ListNode] ) -> ListNode: if not lists: return None if len (lists) == 1 : return lists[0 ] mid = len (lists) // 2 left = self .mergeKLists(lists[:mid]) right = self .mergeKLists(lists[mid:]) return self .mergeTwoLists(left, right) def mergeTwoLists (self, l1: ListNode, l2: ListNode ) -> ListNode: dummy = ListNode(0 ) current = dummy while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else : current.next = l2 l2 = l2.next current = current.next current.next = l1 if l1 else l2 return dummy.next
3.4 LeetCode 241. Different Ways to Add Parentheses 这个问题是一个典型的分治问题，我们可以根据运算符将表达式分成左右两部分，然后递归地计算左右两部分的结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution : def diffWaysToCompute (self, expression: str ) -> List [int ]: if expression.isdigit(): return [int (expression)] res = [] for i, char in enumerate (expression): if char in ['+' , '-' , '*' ]: left = self .diffWaysToCompute(expression[:i]) right = self .diffWaysToCompute(expression[i+1 :]) for l in left: for r in right: if char == '+' : res.append(l + r) elif char == '-' : res.append(l - r) else : res.append(l * r) return res
4. 分治算法的应用场景
排序算法 ：如归并排序、快速排序。大整数乘法 ：如 Karatsuba 算法。矩阵乘法 ：如 Strassen 算法。最近点对问题 ：在平面上找到距离最近的两个点。快速傅里叶变换（FFT） ：用于多项式乘法和大整数乘法。
5. 分治算法的优势与局限性 优势：
通过递归，可以将复杂问题简化。
适合并行计算，不同的子问题可以在不同的处理器上解决。
对于某些问题，如归并排序，可以获得很好的时间复杂度。
局限性：
递归可能导致栈溢出。
有时候分治算法可能不如动态规划等其他方法效率高。
合并子问题的解可能是一个复杂的操作。
6. 分治算法的技巧与注意事项
选择合适的分解点 ：分解问题时，选择合适的分解点很重要，这可能影响算法的效率。处理边界情况 ：注意处理子问题规模很小或为空的情况。避免重复计算 ：某些情况下，可以使用记忆化来避免重复计算相同的子问题。结合其他算法 ：分治算法可以与其他算法（如动态规划、贪心）结合使用。
7. 分治与其他算法范式的比较
分治 vs 动态规划 ：动态规划通常用于有重叠子问题的情况，而分治更适合子问题相互独立的情况。分治 vs 贪心 ：贪心算法每步做出局部最优选择，而分治算法将问题分解后递归求解。分治 vs 回溯 ：回溯算法是穷举搜索的一种方法，而分治算法focus在问题的分解和合并。
结语 分治算法是一种强大的问题解决策略，特别适合那些可以自然地分解为相似子问题的问题。通过本文的学习，我们深入了解了分治算法的基本原理、LeetCode 实战应用以及各种技巧和注意事项。在实际应用中，要根据具体问题的特点，选择是否使用分治策略，并可能需要结合其他算法技巧来优化解决方案。通过不断练习和总结，我们可以在算法解题中越来越熟练地运用分治思想，解决各种复杂问题。
