Python面试碰壁?一招教你搞定面试算法系列——分治算法三步走

标签: 程序员  编程语言  python

很多同学让出一些关于 Python面试相关的教程,这不来了!这次先将大家感兴趣算法方面的!

主要思想

分治算法,即 分而治之:把一个复杂问题分成两个或更多的相同或相似子问题,直到最后子问题可以简单地直接求解,最后将子问题的解合并为原问题的解。

归并排序就是一个典型的分治算法。

三步走

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

1.分解:分解原问题为结构相同的 子问题(即寻找子问题)

2.解决:当分解到容易求解的边界后,进行 递归求解

3.合并:将子问题的解合并成原问题的解
在这里插入图片描述
这么一说似乎还是有点抽象?那我们通过经典的排序算法 归并排序来体验一下分治算法的核心思想。

归并排序

思想

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

因此,在归并排序中的子问题就是: 使子序列有序。

三步走

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

1.分解:将序列划分为两部分

2.解决:递归地分别对两个子序列进行归并排序

3.合并:合并排序后的两个子序列

举例

来看一个具体的例子。

现在有一个待排序的序列:
10, 4, 6, 3, 8, 2, 5, 7

先对序列进行分解,把该序列一分为二,直到无法拆分为止。整个拆分过程如下:
在这里插入图片描述
然后对分解出的序列进行两两排序与合并:

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

整个归并排序完整过程如下:
在这里插入图片描述
实现

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

真题演练

为运算表达式设计优先级

题目描述

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

示例 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.合并:根据运算符合并左右两部分的解,得出最终解

其实算法相关的 Python面试教程前面有跟大家讲到,也可以找一下前面的内容。

实现

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.合并子问题的解

版权声明:本文为xuange01原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xuange01/article/details/103325084