欢迎光临散文网 会员登陆 & 注册

刷题第十七天

2023-08-20 22:48 作者:叶荜莉  | 我要投稿

134. 加油站:

这题很有意思,再做一遍还是做不出来。这题的思路是画出折线图,找出最低点。首先的关键点在于能否到达,因此0点的油量是0,到达下一个点的油量是gas[0]-cost[0]。其次是最后结果要多+1,这里的理解可以是最低点是耗油量最高的,那我势必从最低点的下一点出发,这样可以积攒更多的油量应对这一次的消耗。

135. 分发糖果:

这题要考虑左边的也要考虑右边的,可以先遍历一遍,先考虑左边的,如果比自己左边的大,糖果数就比左边多加1。之后再考虑右边,从末尾开始遍历,如果比自己右边大,就取右边+1和自身糖果数的较大值。

860. 柠檬水找零:

这题把当前收到的5块十块记录下来,如果收到了十块,当前有五块,就将十块加一,五块减一,如果找不开,就返回false,如果收到了二十,先找一张十块和一张五块的,如果没有十块,就找三张五块的,还是没有就返回false。

406. 根据身高重建队列:

遇到这种有两个参数的题目,往往只需要让两个参数按照相反的方式排列。这题采用的是身高由高到低,身高一致则属性低的在前。再遍历一次,依次插入在属性值的位置即可。

452. 用最少数量的箭引爆气球:

这题的直观思路就是从头到尾打重叠的部分。先对数组从小到大排序,cnt初始值设为1,开始遍历,如果当前的左边界比前一个的右边界大,说明不重合,cnt++。否则更新当前的右边界为当前和前一个中较小的右边界。

435. 无重叠区间:

这题和452其实是一样的思路,452也是算重叠区间。

763. 划分字母区间:

首先遍历一遍,用一个map记录字符出现过的最后的位置下标。然后再从0开始遍历,记录下0位置字符的最后出现下标为e,再内循环从i到e,在这个范围内的字符的最后下标如果超过e,那就更新e,最后跳出循环,此时的i到e就是符合题目要求的子串了。

56. 合并区间:

这题其实剖开外表,核心思想和763是一样的。先将数组排序,使用一个s和e记录起始和结束位置,如果当前节点的起始位置大于开始位置,那就将s和e记录下来,否则更新e。

738. 单调递增的数字:

这题就是找到开始单调递减的点f,从后向前遍历。如果找到i-1大于i,就让i-1的值减一,因为f要设为9,这样前一个点是要减少一的。






刷题第十七天的评论 (共 条)

分享到微博请遵守国家法律