今日任务：
资料来源：
题目
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
遇见了以前写过的题可还行，这题就是优先去消耗10块，再消耗5块就行。
pythonfrom typing import List
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five_bill_num = 0
ten_bill_num = 0
for bill in bills:
if bill == 5:
five_bill_num += 1
elif bill == 10:
five_bill_num -= 1
ten_bill_num += 1
else:
if ten_bill_num > 0:
ten_bill_num -= 1
five_bill_num -= 1
else:
five_bill_num -= 3
if five_bill_num < 0 or ten_bill_num < 0:
return False
return True
题目
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
这题一开始看的时候完全没弄明白和贪心有什么关系，想了半天之后想到的思路就是先对为0的人先按进行升序排序，然后再对剩下不是0的挨个插入到后面的位置去。
下面这些代码的思路是先按进行降序排序，如果相同则按升序排序。之后对排序后的数组进行循环，以为索引直接插入新数组result即可。这样能够保证每次插入元素时，result里全部都是大于等于要处理的元素的，再按照为下标插入就可以完美符合条件。
pythonfrom typing import List
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (-x[0], x[1])) # 先按x[0]进行降序排序，如果x[0]相同则按x[1]升序排序
result = []
for i in people:
result.insert(i[1], i)
return result
题目
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球[2,8]和[1,6]。 -在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破: - 在x = 2处发射箭，击破气球[1,2]和[2,3]。 - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
提示:
这是重叠区间问题，贪心贪在尽可能多的让同一支箭引爆尽可能重叠的气球（区间）。先对所有气球按区间开始位置排序，再循环并且记录区间结束位置（即气球的），如果下一个区间的结束位置小于记录位置，那么说明这个气球和记录位置对应的气球完全重叠，为了引爆这个更小的气球（更小的区间），将记录位置改为这个更小的区间的结束位置；如果下一个区间的开始位置大于记录位置，那么说明下一个气球和记录位置对应的气球完全不重合，那就可以引爆之前的气球，并且将记录位置更新为下一个区间（气球）的结束位置。
pythonfrom typing import List
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[0])
result = 0
arrow_x = points[0][1]
for i in points:
if i[1] < arrow_x:
arrow_x = i[1]
if i[0] > arrow_x:
result += 1
arrow_x = i[1]
return result + 1
本文作者:御坂19327号
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！