0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

分治算法详解:表达式的不同优先级

算法与数据结构 来源:算法与数据结构 作者:labuladong 2021-01-04 14:04 次阅读

我们号已经写了 动态规划算法,回溯(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 题讲讲什么是分治算法,先看看题目:

1aaef858-48d3-11eb-8b86-12bb97331649.png

简单说,就是给你输入一个算式,你可以给它随意加括号,请你穷举出所有可能的加括号方式,并计算出对应的结果

函数签名如下:

//计算所有加括号的结果
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 * 34 * 5

分治分治,分而治之,这一步就是把原问题进行了「分」,我们现在要开始「治」了

1 + 2 * 3可以有两种加括号的方式,分别是:

(1) + (2 * 3) = 7

(1 + 2) * (3) = 9

或者我们可以写成这种形式:

1 + 2 * 3 = [9, 7]

4 * 5当然只有一种加括号方式,就是4 * 5 = [20]

然后呢,你能不能通过上述结果推导出(1 + 2 * 3) - (4 * 5)有几种加括号方式,或者说有几种不同的结果?

显然,可以推导出来(1 + 2 * 3) - (4 * 5)有两种结果,分别是:

9 - 20 = -11

7 - 20 = -13

那你可能要问了,1 + 2 * 3 = [9, 7]的结果是我们自己看出来的,如何让算法计算出来这个结果呢?

这个简单啊,再回头看下题目给出的函数签名:

//定义:计算算式 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
right=diffWaysToCompute(input.substring(i+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;
}

有了刚才的铺垫,这段代码应该很好理解了吧,就是扫描输入的算式input,每当遇到运算符就进行分割,递归计算出结果后,根据运算符来合并结果。

这就是典型的分治思路,先「分」后「治」,先按照运算符将原问题拆解成多个子问题,然后通过子问题的结果来合成原问题的结果

当然,一个重点在这段代码:

//basecase
//如果res为空,说明算式是一个数字,没有运算符
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}

递归函数必须有个 base case 用来结束递归,其实这段代码就是我们分治算法的 base case,代表着你「分」到什么时候可以开始「治」。

我们是按照运算符进行「分」的,一直这么分下去,什么时候是个头?显然,当算式中不存在运算符的时候就可以结束了。

那为什么以res.isEmpty()作为判断条件?因为当算式中不存在运算符的时候,就不会触发 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;
}

当然,这个优化没有改变原始的复杂度,只是对一些特殊情况做了剪枝,提升了效率。

最后总结

解决上述算法题利用了分治思想,以每个运算符作为分割点,把复杂问题分解成小的子问题,递归求解子问题,然后再通过子问题的结果计算出原问题的结果。

把大规模的问题分解成小规模的问题递归求解,应该是计算机思维的精髓了吧,建议大家多练~

责任编辑:xj

原文标题:分治算法详解:表达式的不同优先级

文章出处:【微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。


声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4610

    浏览量

    92860
  • 分治法
    +关注

    关注

    0

    文章

    3

    浏览量

    5757

原文标题:分治算法详解:表达式的不同优先级

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    详解nginx中的正则表达式

    前言,我这里验证的nginx-v1.23.2单机环境下的nginx中的正则表达式、location路径匹配规则和优先级
    的头像 发表于 12-03 09:59 167次阅读
    <b class='flag-5'>详解</b>nginx中的正则<b class='flag-5'>表达式</b>

    Verilog表达式的位宽确定规则

    很多时候,Verilog中表达式的位宽都是被隐式确定的,即使你自己设计了位宽,它也是根据规则先确定位宽后,再扩展到你的设计位宽,这常常会导致结果产生意想不到的错误。
    的头像 发表于 10-22 15:41 471次阅读
    Verilog<b class='flag-5'>表达式</b>的位宽确定规则

    nginx中的正则表达式和location路径匹配指南

    前言,我这里验证的nginx-v1.23.2单机环境下的nginx中的正则表达式、location路径匹配规则和优先级
    的头像 发表于 09-29 16:02 748次阅读
    nginx中的正则<b class='flag-5'>表达式</b>和location路径匹配指南

    freertos中断优先级在哪设置

    FreeRTOS是一个流行的实时操作系统,它广泛应用于嵌入式系统开发。在FreeRTOS中,中断优先级是一个重要的概念,因为它决定了中断处理的顺序和响应时间。 1. 理解中断优先级 在讨论如何设置
    的头像 发表于 09-02 14:17 675次阅读

    求助,以下恒流源电路Io的计算表达式怎么计算?

    这个恒流源电路Io的计算表达式怎么计算,求给出详细计算过程
    发表于 08-22 08:16

    TestStand表达式中常用的语法规则和运算符使用

    TestStand也有自己的语言嘛?在回答这个问题之前大家可以想一下在使用TestStand时有一个和语言密切相关的属性。没错那就是表达式(Expressions),在这篇文章中,小编将以Q&A的方式来带着大家来理解并熟悉TestStand表达式中较为常用的一些语法规则以
    的头像 发表于 08-15 18:10 1401次阅读
    TestStand<b class='flag-5'>表达式</b>中常用的语法规则和运算符使用

    鸿蒙原生应用元服务开发-仓颉基本概念表达式(二)

    ,以下程序使用 do-while 表达式,基于蒙特卡洛算法,近似计算圆周率的值: import std.random.* main() { let random = Random() var
    发表于 08-09 14:26

    鸿蒙原生应用元服务开发-仓颉基本概念表达式(一)

    在一些传统编程语言中,一个表达式由一个或多个操作数(operand)通过零个或多个操作符(operator)组合而成,表达式总是隐含着一个计算过程,因此每个表达式都会有一个计算结果,对于只有操作数而
    发表于 08-08 10:27

    求助,有关表达式选项卡(ADS)的问题求解

    你好。 我看不到表达式选项卡中的某些变量值。 数组的大小显然是 256,但我最多只能看到 100。 请问问题出在哪里? 谢谢。
    发表于 06-03 06:23

    mapgis属性筛选表达式

    篇文章中,我们将详细讨论MapGIS的属性筛选表达式,包括语法、操作符和函数等。 属性筛选表达式是一种在MapGIS中用于指定要素选择条件的代码。它由一组操作符、函数和属性字段组成,用于描述要筛选的要素的特征。在MapGIS中,属性筛选
    的头像 发表于 02-25 10:58 1622次阅读

    西门子博途的算术表达式

    算术表达式既可以是一个数字值,也可以是由带有算术运算符的两个值或表达式组合而成。 算术运算符可以处理当前 CPU 所支持的各种数据类型。如果在该运算中有 2 个操作数,那么可根据以下条件来确定结果的数据类型。
    的头像 发表于 01-24 11:36 1003次阅读

    你还不会gvim正则表达式?一文搞懂!

    gvim正则表达式常在命令行模式下使用,一般用于文本文件字符串的替换、删除等操作。
    的头像 发表于 01-19 16:47 1178次阅读

    rs触发器的逻辑表达式

    逻辑表达式是描述逻辑关系的符号表示,可以用于定义和描述各种电路和逻辑操作。在逻辑电路中,RS触发器是一种基本的存储器元件,也被称为锁存器。 RS触发器是由两个与门组成的,其输出互相连接,形成一个反馈
    的头像 发表于 01-12 14:09 3143次阅读

    华为和思科默认路由优先级

    优先级值不同,则优先级值最小的为最优路由(无论开销值是否相同,另一种理解就是对不同路由来源或路由协议之间的比较)。
    的头像 发表于 01-11 10:47 1210次阅读

    GD32如何配置中断优先级分组以及中断优先级

    使用GD32 MCU的过程中,大家可能会有以下疑问:中断优先级如何配置和使用?
    的头像 发表于 01-10 10:30 3089次阅读
    GD32如何配置中断<b class='flag-5'>优先级</b>分组以及中断<b class='flag-5'>优先级</b>