860.柠檬水找零
我们维护三种金额的数量:five,ten,twenty
有如下三种情况:
- 账单是5:five + 1,无需找零
- 账单是10:ten + 1,找零一张5元(five - 1)
- 账单是20:twenty + 1,找零一张10元一张5元(ten - 1, five -1),或找零三张5元(five -3)
前两种情况都是固定策略,第三种情况存在两种策略。
如果账单是20,应该优先消耗一个10元一个5元,而不是三个5元。为什么?
因为10元只能用来给20元账单找零,而5元既可以给20元或10元账单找零。
5元更万能,因此使用贪心策略,优先消耗10元,可以给更多的账单找零。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten, twenty = 0, 0, 0
for bill in bills:
# 5元账单
if bill == 5:
five += 1
# 10元账单
elif bill == 10:
ten += 1
if five > 0:
five -= 1
else:
return False
# 20元账单
elif bill == 20:
twenty += 1
# 优先使用10元找零
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True
406.根据身高重建队列
如果同时考虑两个属性 h 和 k,那么很容易顾此失彼。
我们首先考虑身高属性 h,由于 k 描述的是前面有
k
个身高大于或等于h
的人,因此更高的应该排在前面,我们按照身高 h 降序排序数组。对于身高相同的人,按照 k 升序排序。接着考虑属性 k,我们将 k 当作索引,重新安排排序后的数组即可得到结果。举个例子,[5, 1],意味着此人之前有 1个 身高 不矮于5 的人,由于先前已经按照身高排序,因此此人应该被安插在 第二个 位置。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 排序
# -x[0]:按照身高h降序排序
# x[1]:如果身高h相同,按照人数k降序排列
people.sort(key = lambda x: (-x[0], x[1]))
res = []
# 重建
for p in people:
# 以 k 为索引重建队列
res.insert(p[1], p)
return res
452.用最少数量的箭引爆气球
思路:按照左边界对数组进行排序,通过判断当前气球的左边界 是否大于 上一个气球的右边界来判断是否重叠。需要注意的是,存在2个甚至更多气球重叠的情况,因此每次发现重叠气球的情况时,我们需要寻找一个最优的射击位置:重叠气球中最小的右边界。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
# 按左边界排序
points.sort(key = lambda x: x[0])
result = 1
for i in range(1, len(points)):
if points[i][0] > points[i-1][1]:
result += 1
# 寻找最优射击位置
else:
points[i][1] = min(points[i-1][1], points[i][1])
return result