860. 柠檬水找零
- 思路
- example
- bills[i] 不是 5 就是 10 或是 20
- 应找零： bills[i] - 5
- hash[5] = 剩余张数，hash[10] 记录每个面值的张数
- 找零顺序：贪心。先大后小。
- 别忘了更新余额，每个人净收$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. 根据身高重建队列
- 思路
- example
- people顺序是乱的，需要重排成queue，使得
-
: 表示前面正好有
-
- 题目数据确保队列可以被重建
-
"遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。"
-
- 复杂度. 时间：
, 空间:
先按身高从大到小排序
先处理身高高的，相同身高按照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. 用最少数量的箭引爆气球
- 思路
- example
- 重叠区间：排序 + 贪心
先排序points (按x[0]坐标)
从左到右遍历每个区间左端点
更新当前重叠区间的范围:[left, right] (其实left信息不需要），如果当前区间起点大于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
