題目簡介
860. 檸檬水找零
在檸檬水?dāng)偵舷恳槐瓩幟仕氖蹆r為 5 美元狂秦。顧客排隊購買你的產(chǎn)品捧灰，（按賬單 bills 支付的順序）一次購買一杯。
每位顧客只買一杯檸檬水麻顶，然后向你付 5 美元遍略、10 美元或 20 美元。你必須給每個顧客正確找零崖咨，也就是說凈交易是每位顧客向你支付 5 美元锻拘。
注意，一開始你手頭沒有任何零錢击蹲。
給你一個整數(shù)數(shù)組 bills 署拟，其中 bills[i] 是第 i 位顧客付的賬。如果你能給每位顧客正確找零际邻，返回 true 芯丧，否則返回 false 。
406. 根據(jù)身高重建隊列
假設(shè)有打亂順序的一群人站成一個隊列世曾，數(shù)組 people 表示隊列中一些人的屬性（不一定按順序）缨恒。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi 谴咸，前面 正好 有 ki 個身高大于或等于 hi 的人。
請你重新構(gòu)造并返回輸入數(shù)組 people 所表示的隊列骗露。返回的隊列應(yīng)該格式化為數(shù)組 queue 岭佳，其中 queue[j] = [hj, kj] 是隊列中第 j 個人的屬性（queue[0] 是排在隊列前面的人）。
452. 用最少數(shù)量的箭引爆氣球
有一些球形氣球貼在一堵用 XY 平面表示的墻面上萧锉。墻面上的氣球記錄在整數(shù)數(shù)組 points 珊随，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球。你不知道氣球的確切 y 坐標(biāo)柿隙。
一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出叶洞。在坐標(biāo) x 處射出一支箭，若有一個氣球的直徑的開始和結(jié)束坐標(biāo)為 xstart禀崖，xend衩辟， 且滿足 xstart ≤ x ≤ xend，則該氣球會被 引爆 波附∫涨纾可以射出的弓箭的數(shù)量 沒有限制 。 弓箭一旦被射出之后掸屡，可以無限地前進封寞。
給你一個數(shù)組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數(shù) 仅财。
初見思路
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five=ten=0 #手中的5狈究，10個數(shù)
for bill in bills:
if bill==5:
five+=1
elif bill==10:
if five==0:return False
five-=1
ten+=1
else:
if five>0 and ten>0:
five-=1
ten-=1
elif five>=3:
five-=3
else: return False
return True
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (-x[0], x[1]))
print(people)
que = []
for p in people:
que.insert(p[1], p)
return que
- 重要的是尋找不相交的區(qū)間，也可以先合并可合并區(qū)間再計算盏求，或者是可以采用下方這種一次遍歷的方式谦炒。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if len(points) == 1:
return 1
points.sort(key=lambda x:x[0])
print(points)
il,ir = points[0][0],points[0][1]
cnt = 1
for interval in points:
if interval[0] > ir:
cnt += 1
il,ir = interval[0],interval[1]
else:
il = max(interval[0], il)
ir = min(interval[1], ir)
return cnt
復(fù)盤思路
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
