贪心算法860|406|452
860柠檬水找零
class Solution: def lemonadeChange(self, bills: List[int]) -> bool: five = 0 ten = 0 for i in range(len(bills)): if bills[i] == 5: five += 1 elif bills[i] == 10: if five > 0: five -= 1 ten += 1 else: return False elif bills[i] == 20: if five > 0 and ten > 0: five -= 1 ten -= 1 elif five >= 3: five -= 3 else: return False return True
406根据身高重建队列
class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: sorted_people = sorted(people, key = lambda x: (-x[0], x[1])) for i in range(len(sorted_people)): if sorted_people[i][1] != i: index = sorted_people[i][1] temp = sorted_people.pop(i) sorted_people.insert(index, temp) return sorted_people
452用最少数量的箭引爆气球
class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: if len(points) == 1: return 1 result = 1 sorted_points = sorted(points, key = lambda x: x[0]) for i in range(1, len(sorted_points)): if sorted_points[i][0] > sorted_points[i - 1][1]: result += 1 else: sorted_points[i][1] = min(sorted_points[i - 1][1], sorted_points[i][1]) return result