五分钟学算法之「分治算法」三步走

爱被打了一巴掌 2023-06-19 11:06 36阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

作者 | 江子抑

来源 | 编程拯救世界

## 主要思想 ##

分治算法，即**分而治之**：把一个复杂问题分成两个或更多的相同或相似子问题，直到最后子问题可以简单地直接求解，最后将子问题的解合并为原问题的解。归并排序就是一个典型的分治算法。

在这篇文章中我们将先介绍分治算法的「三步走套路」，然后通过经典的归并排序算法体验一番分治算法的核心，最后再通过真题演练一试身手！

## 三步走 ##

和把大象塞进冰箱一样，分治算法只要遵循三个步骤即可：**分解 -> 解决 -> 合并**。

1.  分解：分解原问题为结构相同的**子问题**（即寻找子问题）
2.  解决：当分解到容易求解的边界后，进行**递归求解**
3.  合并：将子问题的解合并成原问题的解

![分治算法三步走][format_png 1]

分治算法三步走

这么一说似乎还是有点抽象？那我们通过经典的排序算法**归并排序**来体验一下分治算法的核心思想。

## 归并排序 ##

### 思想 ###

归并排序的思想是：**欲使序列有序，必先使其子序列有序**。即先使得每个子序列有序，然后再将子序列合并成有序的列表。

因此，在归并排序中的子问题就是：**使子序列有序**。

### 三步走 ###

既然已经找到了问题的子问题，是时候套用我们上述的三步走方法了。归并排序的「三步走」如下：

1.  分解：将序列划分为两部分
2.  解决：递归地分别对两个子序列进行归并排序
3.  合并：合并排序后的两个子序列

### 举例 ###

来看一个具体的例子。

现在有一个待排序的序列：

> 10, 4, 6, 3, 8, 2, 5, 7

先对序列进行分解，把该序列一分为二，直到无法拆分为止。整个拆分过程如下：

![序列分解][format_png 2]

序列分解

然后对分解出的序列进行两两排序与合并：

> 10, 4 排序合并后：4, 10  
> 6, 3 排序合并后：3, 6  
> 8, 2 排序合并后：2, 8  
> 5, 7 排序合并后：5, 7  
> ……

整个归并排序完整过程如下：

![format_png 3][]

上部分为「分解」，下部分为「解决」与「合并」

### 实现 ###

def merge_sort(lst):
        # 从递归中返回长度为1的序列
        if len(lst) <= 1:
            return lst          
    
        middle = len(lst) / 2
        # 1.分解：通过不断递归，将原始序列拆分成 n 个小序列
        left = merge_sort(lst[:middle])     
        right = merge_sort(lst[middle:])
        # 进行排序与合并
        return merge(left, right)
    
    def merge(left, right):
        i, j = 0, 0
        result = []
        # 2.解决：比较传入的两个子序列，对两个子序列进行排序
        while i < len(left) and j < len(right):  
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        # 3.合并：将排好序的子序列合并
        result.extend(left[i:])         
        result.extend(right[j:])
        return result

## 真题演练 ##

### 为运算表达式设计优先级 ###

> LeetCode 241. 为运算表达式设计优先级: *https://leetcode-cn.com/problems/different-ways-to-add-parentheses/*

#### 题目描述 ####

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 `+` , `-` 以及 `*`。

示例 1:

输入: "2-1-1"
    输出: [0, 2]
    解释: 
    ((2-1)-1) = 0 
    (2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
    输出: [-34, -14, -10, -10, 10]
    解释: 
    (2*(3-(4*5))) = -34 
    ((2*3)-(4*5)) = -14 
    ((2*(3-4))*5) = -10 
    (2*((3-4)*5)) = -10 
    (((2*3)-4)*5) = 10

#### 思路 ####

对于一个形如 `x op y`（`op` 为运算符，`x` 和 `y` 为数） 的算式而言，**它的结果组合取决于 `x` 和 `y` 的结果组合数**，而 `x` 和 `y` 又可以写成形如 `x op y` 的算式。

因此，该问题的子问题就是 `x op y` 中的 `x` 和 `y`：**以运算符分隔的左右两侧算式解**。

然后我们来进行**分治算法三步走**：

1.  分解：按运算符分成左右两部分，分别求解
2.  解决：实现一个递归函数，输入算式，返回算式解
3.  合并：根据运算符合并左右两部分的解，得出最终解

#### 实现 ####

class Solution:
        def diffWaysToCompute(self, input: str) -> List[int]:
            # 如果只有数字，直接返回
            if input.isdigit():
                return [int(input)]
    
            res = []
            for i, char in enumerate(input):
                if char in ['+', '-', '*']:
                    # 1.分解：遇到运算符，计算左右两侧的结果集
                    # 2.解决：diffWaysToCompute 递归函数求出子问题的解
                    left = self.diffWaysToCompute(input[:i])
                    right = self.diffWaysToCompute(input[i+1:])
                    # 3.合并：根据运算符合并子问题的解
                    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

## 总结 ##

**分治算法的核心是寻找子问题的解**，解题步骤遵循「三步走」：

1.  找到子问题并分解
2.  解决子问题（递归）
3.  合并子问题的解

这里为大家准备了两道练手题，大家赶紧试试手吧：

*  LeetCode 932. 漂亮数组: *https://leetcode-cn.com/problems/beautiful-array*
 *  LeetCode 105. 从前序与中序遍历序列构造二叉树: *https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/*

## 参考资料 ##

*  OI Wiki: 递归 - 分治：*https://oi-wiki.org/basic/divide-and-conquer/*

![音符][format_png 4]

**有热门推荐????**

1.【程序员】[我们就必须承认：这个世界上，有很多问题，就是无解的][Link 1]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了！][Link 2]

![format_png 5][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9VZjFxVmxpYlhldUZFOTNwWkwzZDI5bTFGZTdzQ3hlN21BZm1CRHN1THZ1RHQzMXhhSFBkZk5sMnVIVmJaM2dUUjdad2lhcEw1TVpOT2tNZDVKUEtPbW1nLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9VZjFxVmxpYlhldUZFOTNwWkwzZDI5bTFGZTdzQ3hlN21ZRkFBTlFCaWNidFRsWHJsMTRQVGhOc0o3eEFGckgxSjBVUmxIRjNQTmljNnNScWZWWVdiSFNzQS82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9VZjFxVmxpYlhldUZFOTNwWkwzZDI5bTFGZTdzQ3hlN21EMUtIc2dpYmdCZkRJMjRQTmxhUXJ6aE9IZHBCb0RkaEtKdGY1SXdtU2liaWJpYngyU2IwNkVORGtRLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6L2NaVjJoUnB1QVBpYUpRWFdHeUM5d3JVeklpY2liZ1hheXJnaWJUWWFyVDNBMXl6dHRidGFPMEpsVjIxd01xcm9HWVQzUXRQcTJDN0hNWXN2aWNTQjJwN2RUQmcvNjQwPw?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/100978627
[GitHub]: https://blog.csdn.net/kexuanxiu1163/article/details/100137152
[KMP]: https://blog.csdn.net/kexuanxiu1163/article/details/97071390
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/103051357
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVR1U2ljRUtJcWdpYU9FdG9KaWEwTGcxYTJkWkVLcXlwYzlFcDUzVkpsb0Vobzg4VkdYeVpFSHB2d1paVXR6VnR2RTVJRWliQU5kbFdwUVJRLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png