福州市建设工程造价管理网站,三明城乡建设网站,国外做网站网站安全吗,windows优化大师是官方的吗戳蓝字“CSDN云计算”关注我们哦#xff01;作者 | 江子抑转自 | 编程拯救世界主要思想分治算法#xff0c;即分而治之#xff1a;把一个复杂问题分成两个或更多的相同或相似子问题#xff0c;直到最后子问题可以简单地直接求解#xff0c;最后将子问题的解合并为原问题的… 戳蓝字“CSDN云计算”关注我们哦作者 | 江子抑转自 | 编程拯救世界 主要思想分治算法即分而治之把一个复杂问题分成两个或更多的相同或相似子问题直到最后子问题可以简单地直接求解最后将子问题的解合并为原问题的解。归并排序就是一个典型的分治算法。在这篇文章中我们将先介绍分治算法的「三步走套路」然后通过经典的归并排序算法体验一番分治算法的核心最后再通过真题演练一试身手三步走和把大象塞进冰箱一样分治算法只要遵循三个步骤即可分解 - 解决 - 合并。分解分解原问题为结构相同的子问题即寻找子问题解决当分解到容易求解的边界后进行递归求解合并将子问题的解合并成原问题的解分治算法三步走这么一说似乎还是有点抽象那我们通过经典的排序算法归并排序来体验一下分治算法的核心思想。归并排序思想归并排序的思想是欲使序列有序必先使其子序列有序。即先使得每个子序列有序然后再将子序列合并成有序的列表。因此在归并排序中的子问题就是使子序列有序。三步走既然已经找到了问题的子问题是时候套用我们上述的三步走方法了。归并排序的「三步走」如下分解将序列划分为两部分解决递归地分别对两个子序列进行归并排序合并合并排序后的两个子序列举例来看一个具体的例子。现在有一个待排序的序列10, 4, 6, 3, 8, 2, 5, 7先对序列进行分解把该序列一分为二直到无法拆分为止。整个拆分过程如下序列分解然后对分解出的序列进行两两排序与合并10, 4 排序合并后4, 106, 3 排序合并后3, 68, 2 排序合并后2, 85, 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
真题演练为运算表达式设计优先级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 yop 为运算符x 和 y 为数 的算式而言它的结果组合取决于 x 和 y 的结果组合数而 x 和 y 又可以写成形如 x op y 的算式。因此该问题的子问题就是 x op y 中的 x 和 y以运算符分隔的左右两侧算式解。然后我们来进行分治算法三步走分解按运算符分成左右两部分分别求解解决实现一个递归函数输入算式返回算式解合并根据运算符合并左右两部分的解得出最终解实现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[i1:]) # 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
总结分治算法的核心是寻找子问题的解解题步骤遵循「三步走」找到子问题并分解解决子问题递归合并子问题的解这里为大家准备了两道练手题大家赶紧试试手吧LeetCode 932. 漂亮数组: https://leetcode-cn.com/problems/beautiful-arrayLeetCode 105. 从前序与中序遍历序列构造二叉树: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/参考资料OI Wiki: 递归 - 分治https://oi-wiki.org/basic/divide-and-conquer/福利扫描添加小编微信备注“姓名公司职位”加入【云计算学习交流群】和志同道合的朋友们共同打卡学习推荐阅读扛住100亿次请求——如何做一个“有把握”的春晚红包系统Windows7一个月后停止服务支持亚马逊起诉特朗普向量子计算商用发起挑战英特尔发布Horse Ridge低温控制芯片……扎心12 月全国程序员工资统计半年工资仅涨 500 元数学学渣必备拍照上传分步求解微软解题神器拯救你TIOBE 12 月编程语言排行榜争夺年度编程语言Java、C、Python、C# 即将开战真香朕在看了
