分治算法详解：解析表达式的不同优先级
分治算法详解：解析表达式的不同优先级
我们的账号已经涵盖了动态规划、回溯（DFS）、广度优先搜索（BFS）、贪心、双指针、滑动窗口等多种算法，唯独缺少了分治算法这一环节。今天，我们就来填补这一空缺，以期集齐七种算法，如同召唤神龙一般。
实际上，我认为回溯、分治以及动态规划这类算法应当归为一类，其共同点在于都包含了递归的应用。
回溯算法实则是一种直接了当的算法策略，简而言之，它等同于一种彻底的穷举法。举例来说，若要用回溯算法来寻找子集、全排列或组合，那么你的任务就是进行全面的穷举。在这个过程中，关键在于你是否能够准确无误地避免遗漏或重复计算某些特定情况。
动态规划涉及一种算法类型，其核心任务通常是寻找最大或最小值。此类问题具备显著的最优子结构特性，能够借助状态转移方程，从解决较小子问题的最优解中，逐步推导出解决整个大规模问题的最优解。
分治算法本质上是一种算法理念，它通过将复杂的大问题拆解为若干个较小的子问题，并依据这些子问题的解决结果来构建原问题的解决方案。这一过程与动态规划有相似之处，因此在使用分治算法时，也需遵循一定的规则，即原问题的答案应当能够通过整合各个子问题的答案来得出。
实际上，这些算法之间的界限并不十分明确，有时仅仅是给回溯算法添加一个备忘录，它似乎就转变成了动态规划，而且分治算法在特定情况下也能够通过备忘录来实现剪枝。
个人认为，无需对每种算法的定义过于执着，这些定义不过是些文学性的词汇罢了。只要能解决题目，叫它什么算法都无关紧要。因此，大家还是应该多加练习，通过不断刷题来培养感觉，这样各种算法就能轻松掌握了。
最典型的分治算法就是归并排序了，核心逻辑如下：
voidsort(int[]nums,intlo,inthi){
intmid=(lo+hi)/2;
/******分******/
//对数组的两部分分别排序
sort(nums,lo,mid);
sort(nums,mid+1,hi);
/******治******/
//合并两个排好序的子数组
merge(nums,lo,mid,hi);
}
“运用分治策略的数组排序问题，本质上可以这样解决：首先，将数组的左侧部分进行排序；接着，对右侧部分进行排序；最后，将已排序的两部分合并。如此一来，整个数组的排序不就完成了吗？”
下面来看一道具体的算法题。
添加括号的所有方式
我来借力扣第 241 题讲讲什么是分治算法，先看看题目：
简而言之，这指的是将一个算式提供给你，然后你可以自由地为其添加括号，任务是列举出所有可能的括号组合，并计算出每种组合下的结果。
函数签名如下：
//计算所有加括号的结果
ListdiffWaysToCompute(Stringinput) ;
面对这道题目，首先的感受很可能是它的复杂性。我需要逐一列举出所有可能的括号添加方式，同时，我还要思考这些括号是否合法，以及是否需要考虑计算中的优先级问题。
确实，这一切都需要我们加以考量，然而，我们无需亲自操劳。借助分治策略与递归函数的运用，算法将自动处理所有细节，或许这正是算法所具有的神奇之处，哈哈。
废话不多说，解决本题的关键有两点：
1、不要思考整体，而是把目光聚焦局部，只看一个运算符。
这一点我们在前文曾多次强调，例如在“手把手刷二叉树第一期”中，我们就指出了解决二叉树相关问题的关键在于关注每个节点的具体操作，而非整个树的总体行为。
本质上，处理与递归相关的算法难题，相当于将复杂问题分解为简单部分，你需要锁定一个细微的切入点，进而将问题逐步拆分，化繁为简，最终通过递归函数来逐一解决。
2、明确递归函数的定义是什么，相信并且利用好函数的定义。
这在前文已经多次提及，递归函数会自行调用自身，因此，为了准确执行递归调用，你必须明确函数的功能所在。
下面来具体解释下这两个关键点怎么理解。
我们先举个例子，比如我给你输入这样一个算式：
1 + 2 * 3 - 4 * 5
请问，这个算式有几种加括号的方式？请在一秒之内回答我。
你很可能无法给出答案，这主要是因为括号可以层层包含，要完整地列举出来确实需要付出不少努力。
嵌套结构对于人类来说确实让人感到烦恼，然而在算法面前，处理嵌套括号却相当轻松，只需通过一次递归就能实现一层的嵌套，如果一次递归无法完成，那就多次递归直至问题解决。
因此，作为编写算法的人类，我们只需考虑一个问题：若禁止括号进行嵌套（即仅允许使用单层括号），那么存在多少种不同的括号添加方法？
还是上面的例子，显然我们有四种加括号方式：
(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)
你注意到了吗？实际上，这涉及到依据运算符来划分，对每个运算符的周边部分添加括号，这正是之前所提到的第一个重要步骤。我们不应着眼于整体，而应集中精力于每一个运算符。
现在单独说上面的第三种情况：
(1 + 2 * 3) - (4 * 5)
以破折号为界，我们将原先的算式拆解为两个独立的算式：1加2乘以3，以及4乘以5。
分治策略，将问题分解，这一环节已完成了「分」的步骤，接下来我们便要着手进行「治」。
1 + 2 * 3可以有两种加括号的方式分治算法详解：解析表达式的不同优先级，分别是：
(1) + (2 * 3) = 7
(1 + 2) * (3) = 9
或者我们可以写成这种形式：
1 + 2 * 3 =
而4 * 5当然只有一种加括号方式，就是4 * 5 = 。
那么，你能否根据这些结果推断出表达式（1加上2乘以3）减去（4乘以5）可以有多少种不同的括号添加方法，亦或是说，它能够产生多少种不同的计算结果？
显而易见，从(1 + 2 * 3) - (4 * 5)这个算式中，我们可以得出两个不同的答案，它们是：
9 - 20 = -11
7 - 20 = -13
您或许会好奇，我们是通过观察得出了1加2乘以3等于多少的答案，那么，算法又是如何得出这个结果的呢？
这个简单啊，再回头看下题目给出的函数签名：
//定义：计算算式 input 所有可能的运算结果
ListdiffWaysToCompute(Stringinput) ;
这函数显然是用来完成这项任务的，正是我们之前提到的第二个重要环节——确立函数的界定，坚信并运用这一函数的界定。
你无需深究该函数的实现方式，只需坚信其可行性，付诸实践，最终你会发现，它确实能够实现。
那么，针对(1 + 2乘以3)减去(4乘以5)这一示例，我们的计算方法本质上等同于以下这段程序：
ListdiffWaysToCompute("(1+2*3)-(4*5)") {
Listres=newLinkedList<>();
/******分******/
Listleft=diffWaysToCompute("1+2*3");
Listright=diffWaysToCompute("4*5");
/******治******/
for(inta:left)
for(intb:right)
res.add(a-b);
returnres;
}
好的，现在我们已清楚了解了如何计算(1 加 2 乘以 3) 减去 (4 乘以 5) 的例子，相信你已完全掌握了这一计算方法，那么现在我们可以回到我们最初的问题上。
原问题1加2乘以3减去4乘以5是否仅能按照(1加2乘以3)减去(4乘以5)的方式计算？是否只能依据减号进行划分？
不，并非如此，每种运算符都能将原始问题分解为两个较小的子问题，而且分治算法详解：解析表达式的不同优先级，我之前已经详细地列举了所有可能的分解方法。
(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)
因此，我们必须逐一考察所有这些情形，并且有必要对解决方案的代码进行更深入的优化和细化。
ListdiffWaysToCompute(Stringinput) {
Listres=newLinkedList<>();
for(inti=0;i< input.length(); i++) {
charc=input.charAt(i);
//扫描算式input中的运算符
if(c=='-'||c=='*'||c=='+'){
/******分******/
//以运算符为中心，分割成两个字符串，分别递归计算
List
left=diffWaysToCompute(input.substring(0,i));
List
仅当输入子字符串从索引i+1开始时，才允许计算多种方法得到的结果等于right。1));
/******治******/
//通过子问题的结果，合成原问题的结果
for(inta:left)
for(intb:right)
if(c=='+')
res.add(a+b);
elseif(c=='-')
res.add(a-b);
elseif(c=='*')
res.add(a*b);
}
}
//basecase
//如果res为空，说明算式是一个数字，没有运算符
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}
returnres;
}
经过前面的介绍，这段代码的原理应当已经变得清晰，它主要是对输入的算式进行扫描，每当遇到运算符时，便将其分割开，然后通过递归的方式计算出各个部分的结果，最后再根据运算符将计算结果合并起来。
这正是一种典型的分而治之的策略分治算法在树的路径问题中的应用，它首先进行“分”，将原始问题分解为若干个子问题，接着通过解决这些子问题，最终汇总它们的答案以得出原始问题的解决方案。
当然，一个重点在这段代码：
//basecase
//如果res为空，说明算式是一个数字，没有运算符
if(res.isEmpty()){
res集合中添加了通过将输入字符串转换为整型得到的元素。
}
递归函数需要设立一个基础情况以确保递归能够终止，实际上，这段代码便是我们所说的分治算法的基础情况，它标志着我们在“分”的过程中何时能够转入“治”的阶段。
我们依据运算符来进行划分，如此持续划分，却不知何时才能划到尽头。显而易见，一旦算式中不再出现运算符，划分便可宣告完成。
为何选用res.()作为评判标准？这是因为若算式中缺乏运算符，那么if语句便不会被执行，进而res中便不会增加任何内容。
至此，这道题的解法代码就写出来了，但是时间复杂度是多少呢？
仅从代码本身来看，单凭for循环的迭代次数，我们很难直观地判断出算法的复杂度。因此，我们必须转换思考方式。实际上，本题的目标是寻找所有可能的计算结果，这不正相当于在寻找算式input中所有合法的括号排列组合吗？
那么，对于任意一个算式，究竟可以有多少种不同的括号排列方式呢？这便是广为人知的“卡特兰数”所涉及的内容，其最终呈现的是一个组合数的概念。不过，其推导过程相对较为繁琐，这里我就不详细展开了。对于感兴趣的读者，不妨自行通过网络搜索来获取更多信息。
实际上，本题目还包含一个细微的改进点，即可以通过递归剪枝的方式，削减部分不必要的重复计算。例如，当输入的算式是这样的：
1 + 1 + 1 + 1 + 1
依据算法的运行规则，依照运算符的顺序进行划分分治算法在树的路径问题中的应用，必然会出现以下两种划分情形：
(1 + 1) + (1 + 1 + 1)
(1 + 1 + 1) + (1 + 1)
算法将逐一进行递归处理每种可能性，这实际上等同于进行了多余的运算，因此，我们可以在解法的代码中进行一些调整，引入一个记忆库功能，以此来防止此类重复的计算发生。
//备忘录
HashMap>memo=newHashMap<>();
ListdiffWaysToCompute(Stringinput) {
//避免重复计算
if(memo.containsKey(input)){
returnmemo.get(input);
}
/******其他都不变******/
Listres=newLinkedList<>();
for(inti=0;i< input.length(); i++) {
//...
}
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}
/***********************/
//将结果添加进备忘录
memo.put(input,res);
returnres;
}
当然分治算法在树的路径问题中的应用，此次的改进并未影响原有的复杂程度，它仅仅是对某些特定情况进行了简化处理，从而提高了运作的效率。
最后总结
在解决上述算法问题时，我们采纳了分治的策略，将每个运算符视作分界点，将原本复杂的难题拆解为若干个较为简单的子问题，接着对这些子问题进行递归式的求解，最终根据这些子问题的解答汇总得出原始问题的答案。
将复杂的大问题细化为若干个简单的小问题，并采用递归的方式逐一解决，这恐怕正是计算机科学的核心所在，因此强烈推荐大家加强这方面的练习。
