友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Divide and Conquer 分治法

关于分治法的内容，这里继续参考 《算法设计与分析基础》 中的内容。

分治法是按照以下方案工作的。

  1. 将一个问题划分为同一类型的若干子问题，子问题最好规模相同。

  2. 对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。

  3. 有必要的话，合并这些子问题的解，以得到原始问题的答案。

分治法
Figure 5. 分治法

从字面上分析就可以看到有哪些步骤：

  • 分-分解-将问题分解为规模更小的子问题，子问题最好相同或相似；

  • 治-求解-将这些规模更小的子问题逐个击破；

  • 合-合并-将已解决的子问题合并，最终得出原问题的解；

从上述步骤中我们可以看出，分治算法一般适用满足以下条件的场景：

  1. 问题规模缩小到一定的程度就可以很容易解决；

  2. 问题可以分解为若干个规模较小的相同问题；

  3. 问题分解出的若干子问题的解可以合并为该问题的解；

  4. 每个子问题都是独立的，相互之间没有交集。（这是区别分治法与减）

在“分”的过程中，我们尽可能让分解出的子问题与原始问题相似，而规模更小。这刚好符合递归的特性。因此，分治法往往与递归联系在一起。

在分治法最典型的运用中，问题规模为 n 的实例被划分为两个规模为 n/2 的实例。更一般的情况下，一个规模为 n 的实例可以划分为 b 个规模为 n/b 的实例，其中 a 个实例需要求解（这里，a 和 b 是常量，a≥1，b>1）。

\[T(n) = aT(n/b) + f(n)\]

其中，\(f(n)\) 是一个函数，表示将问题分解为小问题和将结果合并起来所消耗的时间

分治法的典型案例如下：

  1. 归并排序

  2. 快速排序

  3. 二叉树的经典遍历算法和其他类似的算法都需要递归处理左右两棵子树

  4. Strassen 算法

  5. 最近对问题

  6. 凸包问题

分治法对分治出的部分需要分别处理，进行分开的单独计算，而减治法则利用了"一个问题给定实例的解和同样问题较小实例的解之间的关系"，只针对部分子问题求解，减治掉的那部分就不需要了。

减常因子的减治法也可以看做是分治的变种。

经典题目

  1. 4. Median of Two Sorted Arrays

  2. 23. 合并 K 个升序链表

  3. 53. 最大子数组和

  4. 105. Construct Binary Tree from Preorder and Inorder Traversal

  5. 106. Construct Binary Tree from Inorder and Postorder Traversal

  6. 108. Convert Sorted Array to Binary Search Tree

  7. 109. Convert Sorted List to Binary Search Tree

  8. 148. 排序链表

  9. 169. Majority Element

  10. 190. Reverse Bits

  11. 191. Number of 1 Bits

  12. 215. 数组中的第K个最大元素

  13. [0218-the-skyline-problem]

  14. 240. Search a 2D Matrix II

  15. [0315-count-of-smaller-numbers-after-self]

  16. 324. Wiggle Sort II

  17. [0327-count-of-range-sum]

  18. 347. 前 K 个高频元素

  19. [0372-super-pow]

  20. 395. Longest Substring with At Least K Repeating Characters

  21. [0427-construct-quad-tree]

  22. [0493-reverse-pairs]

  23. [0558-logical-or-of-two-binary-grids-represented-as-quad-trees]

  24. 654. Maximum Binary Tree

  25. [0889-construct-binary-tree-from-preorder-and-postorder-traversal]

  26. 912. Sort an Array

  27. [0918-maximum-sum-circular-subarray]

  28. [0932-beautiful-array]

  29. [0973-k-closest-points-to-origin]

  30. [1274-number-of-ships-in-a-rectangle]

  31. [1382-balance-a-binary-search-tree]

  32. [1569-number-of-ways-to-reorder-array-to-get-same-bst]

  33. [1649-create-sorted-array-through-instructions]

  34. [1738-find-kth-largest-xor-coordinate-value]

  35. [1763-longest-nice-substring]

  36. [1982-find-array-given-subset-sums]

  37. [1985-find-the-kth-largest-integer-in-the-array]

  38. [2031-count-subarrays-with-more-ones-than-zeros]

  39. [2179-count-good-triplets-in-an-array]

  40. [2343-query-kth-smallest-trimmed-number]

  41. [2407-longest-increasing-subsequence-ii]

  42. [2426-number-of-pairs-satisfying-inequality]

  43. [2519-count-the-number-of-k-big-indices]

  44. [2613-beautiful-pairs]

  45. [2792-count-nodes-that-are-great-enough]

  46. [3109-find-the-index-of-permutation]

  47. [3165-maximum-sum-of-subsequence-with-non-adjacent-elements]

← Previous: Decrease and Conquer 减治法 | ↑ Up: LeetCode 解题笔记 | Next: Transform and Conquer 变治法 →