专栏首页后端技术【leetcode】栈

【leetcode】栈

1. 895. Maximum Frequency Stack

思路 要想到用多个stack来解决问题,如下图所示构建数据结构

  • problem 146
  • problem 460

2. 880.Decoded String at Index

思路 用size表示在i处,字符串进行解码后的长度。 如果有一个解码后的字符串为appleappleappleappleappleapple,且K=24,那么答案相当于在字符串apple中求K = 4的字符。即size=26,K=24的问题可转化为size=5,K=4的问题。 利用这一点可以先找到刚好size>=K的位置,再反向遍历S,不断化简问题,最后求得答案。

3. 856. Score of Parentheses

思路 用一个stack<int>解决问题。用-2表示左括号,-1表示右括号(事实上-1没用上)。 遇到左括号就放入-2(左括号)。 遇到右括号就把栈内的数依次取出,直到遇到-2(左括号)。如果中途没有遇到-2以外的其它数字,就把1放入栈;否则,把取出来的数求和,乘以2,放回栈中。 最后要记得把栈中的数取出求和。

4. 94. Binary Tree Inorder Traversal

思路 用一个stack<TreeNode *>解决问题。先尽可能往左地把节点放入栈。 每次取出节点并访问,再对它的右节点尽可能往左地放入栈即可。

5. 907. Sum of Subarray Minimums

思路 有两种做法,用数组或者increasing stack

6. 331. Verify Preorder Serialization of a Binary Tree

思路 有几种思路:

  1. 用非叶节点和叶节点的入度与出度的特征判断
  2. 用“空位”判断。叶节点会占用一个空位,非叶节点占用一个空位后会多出两个空位。
  3. 我的思路则是:把它看成程序的一次递归调用,非“#”字符代表函函数的递归调用,“#”代表调用函数并返回了值。每个非“#”字符都应当调用两次递归函数,再返回自己的返回值(返回一个“#")。最终如果只剩下“#”说明函数正常返回。

我对这个的理解是: 剩余的可放置字符空位按照先序排序。 每次遇到一个字符,就把它放置在剩余空位的第一个(按照先序顺序中的第一个)。 因此,在放置过程中,空位不应当用尽。且把所有字符放置完成时,所有空位应当用尽。

7. 853. Car Fleet

思路 把车按离终点的距离从远到近排列。 车队的到达时间取决于排在最前面的那辆车。 从远到近遍历车辆,如果上一辆车到达终点的时间比这一辆车快,就合并把上一辆车合并到当前车队里。然后把当前车队放入栈。 最后,栈里面的元素数量就是车队数量。

思路 采用贪婪原则,从后往前遍历数组,维持一个从栈底到栈顶的递减栈,让s2尽可能地大(这样找到s1 < s2时就可以返回true了)。 所以s2的寻找分两步:

  1. 找到一个s2
  2. 尽可能地让s2变大

算法 从后往前遍历数组,维持一个从栈底到栈顶的递减栈。 每次遇到一个数,如果比栈顶大,就循环把栈顶弹出,并且把s2设置为最后弹出的数(因为维护的是递减栈,最后弹出的数是比当前数小的数中最大的,也就是说,它是s2的最佳候补)。 由于s2每次都被设置为被弹出的数,而且这些数字都比新栈顶小,可以发现,栈里的元素都比s2大,也是遍历过的数中比s2大的所有数,且其中至少有一个数是可以作为s3的(这一段助于理解,意思是栈内的数包含了s2的所有候补)。 也就是说,当s2被设置/更新的时候,一定已经找到了一个s3(至于是多少并不重要)。所以我们如果遇到某个数小于s2,就说明找到了s1,就可以返回true了。所以在遍历的过程中我们主要做2件事:

  1. 设置/更新s2
  2. 寻找s1

9. 402. Remove K Digits

思路 从前往后遍历数字,如果某一位的数字比下一位大,说明只要删除这一位,让下一位数字来代替这一位,就可以让整个数字变小。

所以维护一个非递减栈,从前向后遍历每一位,循环把比当前位大的栈顶弹出,直到k的次数用尽,或者栈弹光了。再把当前位放进栈里面。 遍历以后,如果给的k足够大,栈里的元素从栈底到栈顶,应当是非递减排列的。 如果还有剩余的k的次数,就高位往低位删除数字(因为高位的数字比较大。同样位数的数字中,位数越低,就应当放置越小的数字,而把大的数字留在高位)。 最后删除前导“0”。 另外补充个细节:如果全部字符删除掉了,说明答案是0,就返回“0”。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Failed to download repo] [connect ETIMEDOUT 192.30.255.112]

    平凡的学生族
  • 分析replace into

    三种语法似乎让人眼花缭乱,但我们首先要明确一点:replace into做的是什么,这样它后面不管跟的是values、select还是set都不重要。

    平凡的学生族
  • jrebel远程部署

    平凡的学生族
  • 『互联网架构』软件架构-springcloud分布式链路跟踪sleuth(105)

    PS:5年前就见过别人演示这种系统,当时才开始搞分布式系统,现在想想确实没有你想不到的功能,只有你做不到的,分布式链路跟踪确实是开发和运维的神奇,良好的定位问题...

    IT故事会
  • Android 蓝牙开发(3)——蓝牙的详细介绍

    蓝牙技术最初是由爱立信创制的。技术始于爱立信公司 1994 方案,它是研究在移动电话和其他配件间进行低功耗、低成本无线通信连接的方法。发明者希望为设备间的通讯创...

    开发者
  • 10 亿图片仅需 17.7微秒:Facebook AI 实验室开源图像搜索工具Faiss

    【新智元导读】Facebook的 FAIR 最新开源了一个用于有效的相似性搜索和稠密矢量聚类的库,名为 Faiss,在10亿图像数据集上的一次查询仅需17.7 ...

    新智元
  • vue-cli的项目结构

    这篇文章对纯新手友好,所以有过任何vue开发经验的人可以出门左转啦!这篇文章献给我的homie苏蕾儿童鞋,让她在学习vue项目的时候少走一点弯路(径直冲向末路哈...

    眯眯眼的猫头鹰
  • PowerBI 默认地图最佳实践

    此前写过PowerBI地图解决方案,但仍然比较复杂,随着PowerBI最近的更新,我们来研究下最佳的使用实践。我们先来看下效果:

    BI佐罗
  • python调试代码举例

    Python自带的pdb库,发现用pdb来调试程序还是很方便的,当然了,什么远程调试,多线程之类,pdb是搞不定的。

    py3study
  • 重磅! Flutter 热修复,生态、跨端计划公布

    就个小时之前,Flutter 的产品经理 Tim Sneath 在官方的 Wiki 页面更新了这份 Roadmap 文档,

    Android技术干货分享

扫码关注云+社区

领取腾讯云代金券