1.分而治之（Divide and Conquer）

分而治之是一种重要的算法设计范式，其核心思想是将一个大问题分解成若干个相同或相似的子问题，直到子问题可以被简单直接解决，然后将子问题的解合并，从而得到原问题的解。

基本步骤：

1. 分解（Divide）：将原问题分解成一系列子问题
2. 解决（Conquer）：递归地解决各个子问题。如果子问题足够小，则直接解决
3. 合并（Combine）：将子问题的解合并成原问题的解

特点：

• 递归结构
• 问题可分解
• 子问题相互独立
• 可合并子问题的解

分而治之的使用场景

分而治之适用于以下情况：

• 问题可以被分解成多个子问题
• 子问题与原问题结构相同
• 子问题之间相互独立
• 子问题的解可以合并

经常被使用的分为以下几部分

归并排序（Merge Sort）
快速排序（Quick Sort）
二分搜索（Binary Search）

优势与局限性

优势：

1. 可以将复杂问题分解为简单问题
2. 适用于并行计算，子问题可以独立解决
3. 通常能产生高效的算法（如O(n log n)的排序算法）

局限性：

1. 递归实现可能带来额外的空间开销
2. 不是所有问题都适合分而治之
3. 合并步骤可能比较复杂

实际应用

1. 问题分析：首先判断问题是否可以被分解
2. 子问题设计：确保子问题与原问题结构相同
3. 边界条件：明确基本情况和终止条件
4. 合并策略：设计高效的合并方法
5. 性能考虑：评估分解和合并的开销

分而治之是一种强大而灵活的算法设计范式，掌握它可以帮助你解决许多复杂问题。在实际应用中，需要根据具体问题特点灵活运用这一思想。

分而治之示例

场景一：归并排序

• 分：把数组从中间一分为二
• 解：递归的对两个子数组进行归并排序
• 合：合并有序子数组

场景二：快速排序

• 分：选基准，按基准把数组分成两个子数组
• 解：递归的对两个子数组进行快速排序
• 合：合并两个子数组

leetcode

• 374.猜数字大小

+ [226.翻转二叉树](https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Finvert-binary-tree%2F)
+ [100.相同的树](https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fsame-tree%2F)
+ [101.对称二叉树](https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fsymmetric-tree%2F)