75100150栈与队列

栈篇

题目71:给你一个字符串 path ,将其转化为更加简洁的linux规范路径。

思路:因为涉及到返回上一级目录,就要用栈。

题目155:设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

MinStack() 初始化堆栈对象。 push(int val) 将元素val推入堆栈。pop() 删除堆栈顶部的元素。 top() 获取堆栈顶部的元素。 getMin() 获取堆栈中的最小元素。

思路:既然要按顺序保存元素,那就不能用单调栈。那最小元素就用另一个辅助栈来记录最小值。

push 入栈的时候,与辅助栈顶的元素比较大小,如果小的话,也入辅助栈。pop出栈的时候,记得检查一下是否是最小元素,如果是,辅助栈也要pop。如果不是,就不用管。(因为栈顶元素在辅助栈那边也是在最顶的,如果不是栈顶元素,说明没有入辅助栈)

题目224:给你一个只包含 数字加减括号 和 空格 的字符串表达式 s,如:  "(1+(4+5+2)-3)+(6+8)",请实现一个基本计算器来返回它的值。

思路:1. 首先,要把字符串转变成 符号 括号 和 数字 组成的列表。特别是多位数字要小心处理。

2.  因为括号内的要先计算。因此碰到左括号,就先把前面的值和符号(num, sign)入栈,然后初始化num, sign,逐个加减括号内元素,得到一个值。碰到右括号说明括号内计算完毕,弹出之前的(num, sign)作为 prev_num, prev_sign ,然后 num = prev_num + prev_sign * num

题目394:给定一个经过编码的字符串,返回它解码后的字符串。如s = "3[a2[c]]" 返回"accaccacc"

思路:多层括号,务必手动验证一下栈的逻辑。

由于数字是乘上其身后括号里面的字符串。因此可以把已有的字符串和数字做成元组 (pre_char, num) 放入stack. 直到括号里面的字符串解码完毕,碰到右括号,就弹出(pre_char, num) 用 pre_char + num * (括号内解码完毕的字符串)

题目735:给定一个小行星数组 asteroids,正负表示移动方向。找出碰撞后剩下的所有小行星。

碰撞规则:两个小行星相互碰撞,较小的小行星会爆炸。如果两颗小行星大小相同,则两颗小行星都会爆炸。

思路:由于有正负两个方向,stack记录正向移动的小行星。同时有可能有一个负向移动的小行星击穿所有正向行星,因此还要一个away来记录负向行星。

单调栈篇

题目901:设计一个算法返回股票当日价格的 跨度 。跨度 被定义为股票价格小于或等于今天价格的最大连续日数。例如,如果未来 7 天股票的价格是 [100,80,60,70,60,75,85],那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类:StockSpanner() 初始化类对象。int next(int price) 给出今天的股价 price ,返回该股票当日价格的 跨度 。

思路写在代码里了,模拟一遍栈就懂。

队列篇

题目933:写一个RecentCounter类来计算特定时间范围内最近的请求。

RecentCounter() 初始化计数器,请求数为 0 。int ping(int t) 在时间 t 添加一个新请求,并返回在 [t-3000, t] 内发生的请求数。

思路:超过3000的请求就要舍弃。先进先出,用队列。每次请求的时候添加 t ,同时把超过3000的popleft(),然后返回队列的长度。

题目649:Dota2 参议院由D R 两派的参议员组成。他们按senate的顺序逐轮投票。每一位参议员都可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。宣布胜利:如果参议员发现有权利投票的参议员都是 同一个阵营的 ,则游戏胜利。

思路:按顺序行使权力,那最优策略就是让对方最靠前的那个参议院失去权力。因此使用两个队列,分别记录两党参议院的编号。然后逐对比较,编号靠后者失去权力退出游戏。而编号靠前者加入队伍末端,此时编号要加n.

优先队列/堆 篇

题目215: 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。时间复杂度为 O(n) 

思路:堆排序的时间复杂度是O(nlog(n)),所以用堆来实现O(n)算法有些难度。这里我们假设k为远小于n的数。那时间复杂度还能约等于O(n)

题目502:给你 n 个项目。对于每个项目 i ,它都有一个纯利润 profits[i] ,和启动该项目需要的最小资本 capital[i] 。最初,你的资本为 w 。当你完成一个项目时,你将获得纯利润,且利润将被添加到你的总资本中。总而言之,从给定项目中选择 最多 k 个不同项目的列表,以 最大化最终资本 ,并输出最终可获得的最多资本。

思路:本题陷阱很多!首先,把项目按照投资额排序。第二步,由于投资项目个数有限,因此每次投资都要拿到最大的利润。必须用堆!把项目按照利润入最大堆。然后弹出利润最大的项目,更新本金。循环k次。

题目373:给定两个 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值(u,v),其中第一个元素来自nums1,第二个元素来自 nums2 。请找到和最小的 k个数对(u1,v1), (u2,v2) ...(uk,vk)。

思路:i, j 是nums1 nums2 中的索引, i, j 都有可能取到很大。但全部两两相加去排序太浪费时间复杂度。(i+1, j+1) 能够取到的先决条件是(i+1, j)和 (i, j+1)都被取到了。那就可以用类似动态规划的思路,i 为行,j为列。

初始化就把第一行 nums1[0] + nums2[j] 都加入最小堆。每次从最小堆中取出一对数组,然后加入下一行的元素nums1[i+1] + nums2[j]。列取到 j ,意味着下一行的元素nums1[i+1] + nums2[k] k<j 都已经塞进去了,不会遗漏。

题目295:求取数据流的中位数。实现 MedianFinder 类: MedianFinder() 初始化 MedianFinder对象。void addNum(int num) 将数据流中的整数 num 添加到数据结构中。double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。

思路:用两个堆来实现。用最小堆存放数据流中的较大一半元素;用最大堆存放数据流中的较小 一半元素。两个堆形成上下对称的两个倒三角。三角塔尖就是中位数。

添加元素的时候,必须在两个堆中都遍历一遍,才能保证上三角的元素都大于下三角。

题目2336:实现 SmallestInfiniteSet 类:SmallestInfiniteSet() 初始化:无限集包含所有正整数。int popSmallest() 移除并返回该无限集中的最小整数。void addBack(int num) 如果正整数 num 不 存在于无限集中,则将一个 num 添加 到该无限集最后。

肯定不可能真的实现无限集合,那就看功能,满足功能的要求即可。

思路:取正整数的最小值嘛,那肯定从1开始取。如果没有中途添加元素,那就每次按照一个顺序 self.smallest 1 2 3 ...这样返回即可。如果有添加过元素,那就看取出来的按原定顺序取出来的元素self.smallest还是中途添加的元素,如果是中途添加的元素,self.smallest不用+1. 同时在添加过的元素集合self.added_set中丢去这个中途添加的元素。

中途添加元素的功能,如果比当前的最小整数self.smallest大,就根本不用添加。如果小的话,就看有没有在添加过的元素集合self.added_set中,不在,就加入最小堆。

思路:使用排序的集合。由于pop()功能做多用1000次,那就给一个包含[1, 1001]的排列集合就好。每次取最小,就把第一个元素丢出来。添加元素的话,集合随意添加,还带排序。

题目2542:两个长度为n的整数数组nums1和nums2。选择长度为 k 的 子序列,使得:(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 最大。

思路:由于在nums2中,我们取的是最小值。那就可以按照nums2排序,先取到第k个值,此时的nums2[k]就是最小值,然后乘上nums1的累加和,算出得分。然后继续向前遍历,pop掉nums1值最小的那一对,加入新的nums2。如果新的得分更大,就更新。

题目2462:给定整数数组costs和两个整数k 和candidates。costs[i]是雇佣第 i位工人的成本。总共进行k轮雇佣,且每一轮恰好雇佣一位工人。在每一轮雇佣中,从最前面 candidates和最后面 candidates人中选出成本最小的一位工人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。返回雇佣k位工人的总代价。

思路:“如果有多位代价相同且最小的工人,选择下标更小的一位工人” 那这就简单了。每一轮将left, right范围内的工人和下标丢进一个最小堆,每次取出一个。然后根据下表确定范围是在left 还是在right 变化

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,837评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,551评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,417评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,448评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,524评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,554评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,569评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,316评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,766评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,077评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,240评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,912评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,560评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,176评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,425评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,114评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,114评论 2 352

推荐阅读更多精彩内容