LEETCODE-DAY35

本文主要是介绍LEETCODE-DAY35，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

title: LEETCODE-DAY35
date: 2024-03-26 16:11:08
tags:

今日内容：860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球

T1

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:table={5:0,10:0,20:0}for i in range(len(bills)):if bills[i]==5:table[5]+=1elif bills[i]==10:if table[5]<=0:return Falseelse:table[10]+=1table[5]-=1elif bills[i]==20:if table[5]<=0 or table[10]<=0:return False else: table[20]+=1table[10]-=1table[5]-=1return True

输入
bills =
[5,5,10,20,5,5,5,5,5,5,5,5,5,10,5,5,20,5,20,5]
输出
false
预期结果
true

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:table={5:0,10:0,20:0}for i in range(len(bills)):if bills[i]==5:table[5]+=1elif bills[i]==10:if table[5]<=0:return Falseelse:table[10]+=1table[5]-=1elif bills[i]==20:if (5*table[5]+10*table[10]<15) or table[5]<=0:return False else: table[20]+=1table[10]-=1table[5]-=1return True

AC

T2

本题主要难点在于如何将数组按照h从大到小，h相同时k从小到大的方式进行排序

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key=lambda x:(-x[0], x[1]))queue=list()for i in range(len(people)):queue.insert(people[i][1],people[i])return queue

T3

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()l=len(points)for i in range(l):if i>0 and points[i][0]<points[i-1][1]:points[i][1]=points[i-1][1]points.pop(i-1)return len(points)

IndexError: list index out of range
~~~~~~^^^
if i>0 and points[i][0]<points[i-1][1]:

队列长度减小了

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()l=len(points)for i in range(l):if i>0 and i<len(points) and points[i][0]<points[i-1][1]:points[i][1]=points[i-1][1]points.pop(i-1)return len(points)

输入
points =
[[1,2],[2,3],[3,4],[4,5]]
输出
4
预期结果
2

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()l=len(points)for i in range(l):if i>0 and i<len(points) and points[i][0]<=points[i-1][1]:points[i][1]=points[i-1][1]points.pop(i-1)return len(points)

points =
[[3,9],[7,12],[3,8],[6,8],[9,10],[2,9],[0,9],[3,9],[0,6],[2,8]]
输出
5
预期结果
2

问题在于points pop之后指标也会产生变化，所以需要定义一个变量来记录重叠次数

思路：没有重叠时需射l箭，每有一个重叠少射一箭

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()l=len(points)j=0for i in range(l):if i>0 and points[i][0]<=points[i-1][1]:points[i][1]=min(points[i-1][1],points[i][1])j+=1return l-j

AC

这篇关于LEETCODE-DAY35的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---