0%

leetcode-roadmap

推荐站点:

https://qoogle.top/xiaoxu-explaination-leetcode/

https://codetop.cc/

https://codetop.cc/ 微软

227. 基本计算器 II 2012/03/22-23

这道题,用栈是最快速的,可以现场推理思路,完成80%应该不是问题。
但这种表达式,很可能会被考变种,比如加了括号,加了UnaryOp,甚至更难。
括号,UnaryOp或是自定义函数,这几类还是可以通过少量修改代码支持。但要能做到像高级计算器一样的,抵抗各种灵活拷问,我目前知道的万能方法就是,编译器的基本思路,也就是词法-解析-翻译,这种流程。毕竟我们使用的编译器就是这个思路,没有比这个更完善的了。

当然,编译器思路不好写。总结来说,基本思路需要Lexer,Interpreter。如果Token过于复杂,最好加个Parser,Parser解析出AST,Interpreter再遍历AST树,计算结果。

面试时使用这个思路,写代码会慢一点,但是比栈思路,更深更硬核。

双栈思路

一个栈存操作符Op,一个栈存数字Int。双栈思路的核心就是“先算乘除”,所以扫描处理完整个表达式后,Op栈里应该只有加减号,没有乘除号。

但还有一个点要考虑,就是Op里已有+号,此时你扫描到了新的+号,要怎么做?

如果将栈中的+号及时处理了(也就是同优先级优先计算前面的符号),那么整个表达式算完,就只有一个加号或减号,没什么问题。

如果选择了加减号不先算,直接放栈里,就需要注意,之后的计算顺序。举例说明,一个复杂的表达式化简成只剩加减号时,可能是1-2-3,这时候Op栈是“-,-”,Int栈是“1,2,3”,不能再使用栈的pop,那样就变成了1-(2-3),得用list/vector的顺序计算。
(我临时推理时用了这个思路,大概率以后还会这么干😅。我习惯思维是只push进栈,不爱随时pop,最后会统一pop出来计算。大概是觉得这种流程,代码会比较好看。)

还是推荐大家尽量改善自己的思路,选择第一种方式,以免现场推理出来的逻辑不够完备。

单栈

Leetcode官方题解其实是单栈,但如果你亲手写了双栈,你一定会感受到,如果及时计算同优先级的运算符,Op栈最多只会有一个运算符(+/-号),所以不需要栈,一个变量就能保存了。这就是单栈思路,没什么特别。

边界

栈的大体思路都是如此,如果加入括号或是其他二元运算符,都还能work。加入括号的话,请一定要用第一种方式😂,处理起来方便很多,不然思路容易卡住。

如果加入UnaryOp正负号,尤其是负号,也就是说leetcode 227题的表达式中的整数不保证是非负整数,又需要一次变化。巧妙的思路是给“-”打头的表达式开头添“0”,变成“0-正整数”。将所有”(-“替换为”(0-“,用字符串replace,还可以不用改变算法主体代码,很简单。
而如果还加正号,比如“3++4”合理,这种情况就比有负数的情况还要麻烦了。这要求你的算法能,判断第二个+号是和整数结合的正号(Unary Plus)。再扩展下,“3–++2”等等。代码上就得增加一段逻辑,来处理好UnaryOp。这样当然可以work,但是这也暴露了栈思路的一个问题,就是它没有符合逻辑的解析能力。它似乎只是我们在努力的修补规则,“3–++2”是读取了“3-”后发现还是符号,才会开始解释为一元符号,从左到右计算到底是正号还是负号。但按照逻辑,我们应该是将表达式看作3-(-(+(+(2)))),也就是,真的计算的时刻,2是和前面的正负号结合,然后作为整体又跟前面的正负号结合。也就是解析是顺序,计算是倒序,有种递归下降,然后逐层返回结果的感觉。

其实没什么差别,但是我个人觉得,栈的思路是有些勉强的。因此,当学了一点点编译原理后,我就想用编译的思路来解决这道题了。

TODO

所有计算器题目,都总结下。

  1. 双栈,加减括号,注意允许(+4)这种写法出现,但不用考虑1++2。

  2. 双栈,加减乘除,无括号,不用考虑(+4)或一元运算符的情况。

  3. 基本计算器 IV,只可能使用编译器思路来解决了,而且还要能处理变量。

编译器思路

编译器思路,自然是难的,写起来也不够快。但是学习编译器基本原理,我觉得是有意义的,因为底层到程序编译,稍高层的SQL解析,都是这套思路。Parser,Token,blabla。

简单来说,就是用代码实现几行范式。加入新的符号,就修改范式。

比如,只有加减乘除:

加入括号(LPAREN,RPAREN):

再加入一元运算符(正负号):

Parser/Interpreter实现这几条规则就可以了。

91. 解码方法 2021/03/24-25

需要注意dp访问越界的问题。
通常dp[i]负责看第i个元素(索引其实是i-1),就可以保护住需要访问dp[i-1]的dp公式,因为计算dp数组是i从1开始,dp[0]不会越界。
如果dp公式有dp[i-2],不要慌,dp[1]特殊处理后,dp[2]开始又可以通用处理了。

124. 二叉树中的最大路径和 2021/03/26

  • wait zx

224. Basic Calculator 2021/03/31-04/03

s consists of digits, ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.

227类型的题。这个版本由于没有乘除,用Lexer+Interpreter的版本,范式也不难写。

  • TODO 写一下范式

当然更简单的,还是可以使用双栈。

而且建议只记忆双栈,不用去记一些扩展性不够高的思路

注意,test case有”1-(+1+1)”这种。虽然不用考虑1+-1这种写法,但’(‘号后跟’+/-‘号是要被考虑的。
因此是基本的双栈思路,加过滤空格,再加处理’(+/-‘。

具体说下双栈思路。

首先,框架是逐个字符扫描,但考虑到数字可能是多位,所以最方便的做法应该是while i < len(s):,解析数字时i可能会多加点,其他符号只需+1。

再是每个字符c可能是些什么,各自需要如何处理。如果没什么印象,建议逐个分析,有需要的再合并,想不清楚,直接逐个if-else都行,总比写错了强。
所以,逐个看待,伪代码写作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if c is space:
pass
elif c is digit:
# func parse_int TODO
num = parse_int()
# TODO calc or push to nums?
elif c is '(':
# TODO handle '(+/-'
push to ops queue
elif c is ')':
# ops top is '('
ops pop
num = nums.pop()
# TODO calc or push to nums?
elif c is '+' or '-':
push to nums queue

上面就是最详细的分支情况,由于没有乘除,所以分支数量也没什么可以优化的点。注意我写的TODO,基本都应该封装为一个函数,以免主逻辑太难读,给自己增加难度。

特别的,calc or push to nums是最需要注意的一个地方,明显的,两个分支都用到这一逻辑,封成函数是最好的,我命名为calc_with()

而这个数什么时候用来计算,什么时候直接push进栈呢?

举例分析,我想把nums栈顶top和现有的num拿来计算,那么ops栈顶当然得是+/-号,如果栈顶是’(‘,那自然不该算。只需要考虑这一个条件。

如果不计算,直接push。如果pop栈顶计算了一次,之后的结果,该如何处理?

很容易想到,这个结果,还是应该push进栈。但还是应该多思考一下,有没有什么坑?

这一点可能有点不直观,但你可以手写推理或者debug代码测试,就会知道,calc_with()总是在尽力地合并,只有遇到’(‘才会无法合并,导致nums和ops栈多增一个元素。

简单起见,假设只有+号没有-号,某个时刻的栈只能是+(+((+,不会有++(++(++

假设此时ops栈为+(+((+,现有num,ops栈pop出+号,再nums栈里pop一个数num1,计算出结果res,这个res push回nums栈是合理的。无论后面跟什么符号,都能正确处理。

770. 基本计算器 IV

这个题太长了,看的人头皮发麻。但是抽象一下,就能发现,它实际上难点在于括号展开。因为我们已有的知识已经能把一个有括号的表达式解析出来了,可以转成AST树,也可以在解析parse时及时计算。但是,没有包含过“括号展开”的逻辑。

简单的想一下,AST树完全不知道该怎么去实现括号的展开,所以pass。

所以就考虑下parse时及时计算的时候能不能加上“括号展开”。

parse时,可以知道pre_calc * new term的,具体2 * (a-b),new term为(a-b),之前的计算结果为2(简单起见,用数字举例)。

接下来,该怎么做?

应该做到拆出2 * a-2 * b。这一步即括号展开,是此题的核心。题目也暗示了可以理解为2 * a与-2 * b两项,那么也就是2要跟(1 * a)和(-1 * b)都分别乘一下。代码上其实就是for循环。当然(a-b)这个factor得拆成一个数组(2个元素,a和-b)。还需要拆成系数和word,那系数和word怎么对上号呢?

考虑到2 * a + 1 * a能合并为3 * a,主要功劳是在word上,所以以word为key,系数为value是很合适的。

所以可以用dict,{a: 1, b: -1}这样来表示。

再进一步完善,如果是(c * d - 2 * f) * (a - b),那pre_calc,即(c * d - 2 * f),也得用dict来表示。其实pre_calc没有什么特别,就是一个factor,无论是一个数,还是圆括号扩起来的长表达式。所以用一样的规则,{c*d: 1, f: -2},很通用,也合理。

整理思路

  • TODO 写出范式

也就是说,每个factor(不可再拆分的元素)都可以用一组kv来表示,也就是一个dict。一个term是多个dict合并,最终可以得到1个dict(遍历所有dict,体现加法,因为负号作为系数去了,所以可以当作只有加法)。

term和term之间的乘法,也就是dict和dict组合出一个新的dict(二维for循环,体现乘法)。从左到右一个一个组合,最后得到一个dict,即为最后结果。

剑指 Offer 40. 最小的k个数

TopK,面试时也遇到过,我认为heap K最稳定,但面试官更希望我用快排思想,虽然快排思想有一定几率会很慢–最坏O(n^2)。除了复杂度,实际运行,由于现代计算机架构,inner loop可以很快,见wiki。具体的复杂度算法也可以看wiki。不要仅考虑理论复杂度。

不过有个点,我也不知道是不是记错了,面试官当时可能说c++ stl的paritial_sort是快排思想,但实际paritial_sort就是先构建k大小的堆,然后把剩下的都和堆顶比。nth_element才是快排的思路。

核心快排思路见 Quick Sort

最小k个、最大k个,第k大,第k小问题底层都是一样的,快排,变换一下都可以变为“左边<=,pivot,右边>=”这样的格式。类似golang或stl里,pred作为参数传入。