LC吐血整理之Stack & PriorityQueue篇


所有题解方法请移步 github-Leecode_summary

155.最小栈

不知道怎么说,用list的相关属性append pop min list[-1]似乎做的很容易,时间上也过得去,不知道是不是不能这么直接用…. 题解:需要借助辅助栈记录最小值,空间换取时间(是我太年轻,min(list) = O(n)

232.用栈实现队列

232真的有点意思,看完官方题解之后觉得好巧妙啊,尤其是第二个方法,一个用来入队列,一个用来出队列。   还是要注意一下,python没有类似java中的stack和Queue数据结构,并不意味着232和225就直接使用listdeque属性一步到位。

  • deque 实现
    注意,Python中用队列实现栈,只能使用deque().append()deque().pop()或者deque().appendleft()deque().popleft(),具体python实现移步github

225.用队列实现栈

  • deque 实现
    注意,Python中用队列实现栈,只能使用deque().append()deque().popleft()或者deque().appendleft()deque().pop(),具体python实现移步github

150. 逆波兰表达式求值

不知道为啥,我每次做出中等题,评论就说这个题当属easy题,每次做出困难题,平均就说这个题当属medium..我太难了…
思路就是:
① 循环遍历输入数组中的元素
② 如果元素为数字就压入栈,元素为操作符就从栈中弹出两个数字,进行计算
今日份的Tips-1:
本来想,先得到最终加括号的表达式,最后再eval(),一次性得到结果,没想到在13个测试用例报MemoryError,原来eval()也是有长度限制的呀!
具体解决方案:安全地使用Python中的eval,我就没看了,反正用写了另一种方式..

今日份Tips-2:
eval(string),构建string时pop出来的哪个数为除数哪个数为被除数,需要用到str.format(),可设置参数修改顺序,参考:Python format 格式化函数