算法刷题Day 35 柠檬酸找零+根据身高重建队列+用最少数量的箭引爆气球

**算法刷题 Day35**

### 一、柠檬酸找零#### 题目描述有 n 个柠檬，需要找零。每个柠檬的价格为 $1。如果有足够的钱，可以购买 x 个柠檬，则可以获得 x 个柠檬。如果没有足够的钱，可以购买 y 个柠檬，则可以获得 y 个柠檬。

####问题给定 n 个柠檬和找零金额，求出可以购买的最大柠檬数量。

#### 解决方案

def lemonadeChange(bought_lemons, money):
 """
 :param bought_lemons: int, 已经买过的柠檬数量 :param money: int, 找零金额 :return: int, 可以购买的最大柠檬数量 """
 # 每个柠檬价格为 $1 lemon_price =1 # 如果找零金额不足以买一颗柠檬，则返回0 if money < lemon_price:
 return0 # 计算可以购买的最大柠檬数量 max_lemons = min(money // lemon_price, bought_lemons)
 return max_lemons# 测试用例bought_lemons =10 # 已经买过的柠檬数量money =15 # 找零金额print(lemonadeChange(bought_lemons, money)) # 输出:5

def reconstructQueue(people):
 """
 :param people: List[List[int]], 学生列表，每个学生为 [身高, 人数]
 :return: List[List[int]], 重建后的队列 """
 # 按照身高从低到高排序 people.sort(key=lambda x: x[0])
 # 初始化结果队列 result = []
 # 遍历每个学生 for person in people:
 # 找出插入位置，使得该学生的位置尽可能靠近他的朋友 insert_index = next((i for i, p in enumerate(result) if p[0] >= person[0]), len(result))
 # 插入该学生 result.insert(insert_index, person)
 return result# 测试用例people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
print(reconstructQueue(people))

def findMinArrowShots(points):
 """
 :param points: List[List[int]], 气球列表，每个气球为 [高度, 弹弓数量]
 :return: int, 最少数量的箭 """
 # 按照高度从低到高排序 points.sort(key=lambda x: x[0])
 # 初始化结果队列 result = []
 # 遍历每个气球 for point in points:
 # 如果当前气球可以被上一个箭引爆，则不需要额外的箭 if not result or point[0] > result[-1][0]:
 result.append(point)
 # 计算最少数量的箭 return len(result)

# 测试用例points = [[10,16], [2,8], [1,6], [7,12]]
print(findMinArrowShots(points))