860. 檸檬水找零
- 思路
- example
- bills[i] 不是 5 就是 10 或是 20
- 應找零： bills[i] - 5
- hash[5] = 剩余張數(shù)盆顾，hash[10] 記錄每個面值的張數(shù)
- 找零順序：貪心。先大后小目木。
- 別忘了更新余額，每個人凈收$5
- 復雜度. 時間：O(n), 空間: O(1)
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
pre = 0
record = collections.defaultdict(int)
record[5] = 0
record[10] = 0
for i in range(len(bills)):
need = bills[i] - 5
if pre - need < 0:
return False
while need > 5 and record[10] != 0:
need -= 10
record[10] -= 1
while need > 0 and record[5] != 0:
need -= 5
record[5] -= 1
if need > 0:
return False
record[bills[i]] += 1
pre += 5
return True
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
n = len(bills)
five, ten = 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
ten += 1 # !!!
# need = 5
if five <= 0:
return False
five -= 1
elif bill == 20:
need = 15
if ten > 0:
ten -= 1
need -= 10
while need > 0:
if five <= 0:
return False
five -= 1
need -= 5
return True
- 另一個版本
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten = 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five < 1: return False
five -= 1
ten += 1
else:
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five > 2:
five -= 3
else:
return False
return True
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten = 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five < 1:
return False
five -= 1
ten += 1
elif bill == 20:
rest = 15
if ten > 0:
ten -= 1
rest = 5
while rest > 0:
if five > 0:
five -= 1
rest -= 5
else:
return False
return True
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
n = len(bills)
five, ten, twenty = 0, 0, 0
for i in range(n):
if bills[i] == 5:
five += 1
elif bills[i] == 10:
ten += 1
five -= 1
if five < 0:
return False
else:
twenty += 1
rest = 15
if ten > 0: ### 否則就考慮１５＝５＋５＋５
ten -= 1
rest = 5
while rest > 0:
five -= 1
rest -= 5
if five < 0:
return False
return True
406. 根據(jù)身高重建隊列
- 思路
- example
- people順序是亂的，需要重排成queue，使得
-
: 表示前面正好有
-
- 題目數(shù)據(jù)確保隊列可以被重建
-
"遇到兩個維度權衡的時候仇矾，一定要先確定一個維度，再確定另一個維度解总。"
-
- 復雜度. 時間：
, 空間:
先按身高從大到小排序
先處理身高高的贮匕，相同身高按照k從小到大排位，比如說明應該Insert在第
在list上insert即可 (時間復雜度高）
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (-x[0], x[1]))
res = []
for i in range(len(people)):
res.insert(people[i][1], people[i])
return res
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
n = len(people)
people.sort(key=lambda x: (-x[0], x[1]))
res = list()
for i in range(n):
res.insert(people[i][1], people[i])
return res
- 使用兩個鏈表(方便插入操作）刻盐，再轉化為結果list
TBA
452. 用最少數(shù)量的箭引爆氣球
- 思路
- example
- 重疊區(qū)間：排序 + 貪心
先排序points (按x[0]坐標)
從左到右遍歷每個區(qū)間左端點
更新當前重疊區(qū)間的范圍:[left, right] (其實left信息不需要），如果當前區(qū)間起點大于right劳翰，則說明需要使用一個新的箭敦锌。
- 復雜度. 時間：
, 空間: O(n)
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[0])
res = 1
left, right = -float('inf'), float('inf')
for i in range(len(points)):
x0, x1 = points[i][0], points[i][1]
if x0 <= right:
left = x0
if x1 < right:
right = x1
else: # x0 > right
res += 1
left, right = x0, x1
return res
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[0])
left, right = -float('inf'), float('inf')
res = 1
for point in points:
x0, x1 = point[0], point[1]
if x0 > right:
res += 1
right = x1
else: # x0 <= right:
right = min(right, x1)
return res
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[0])
n = len(points)
right = points[0][1]
res = 0
for i in range(1, n):
if points[i][0] > right:
res += 1
right = points[i][1]
else: # !!!
right = min(right, points[i][1])
res += 1 # !!!
return res
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
n = len(points)
points.sort(key=lambda x: x[0]) # !!!
res = 1
right = points[0][1]
for i in range(1, n):
if points[i][0] > right:
res += 1
right = points[i][1]
else: # !!!
right = min(right, points[i][1])
return res
