栈篇
题目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 变化