過年做哪些網(wǎng)站能致富seo概念
【代碼隨想錄訓(xùn)練營】【Day 37】【貪心-4】| Leetcode 840, 406, 452
需強(qiáng)化知識點
- python list sort的高階用法，兩個key，另一種逆序?qū)懛?/li>
- python list insert的用法
題目
860. 檸檬水找零
- 思路：注意 20 塊找零，可以找3張5塊
- 升級版：可以直接用變量記錄次數(shù)，five，ten
class Solution:def lemonadeChange(self, bills: List[int]) -> bool:money_dict = {5:0, 10:0, 20:0}for i in range(len(bills)):money_dict[bills[i]] += 1if bills[i] == 5:continueelif bills[i] == 10:money_dict[5] -= 1if money_dict[5] < 0:return Falseelse:if money_dict[10] > 0 and money_dict[5] > 0:money_dict[10] -= 1money_dict[5] -= 1elif money_dict[5] > 2:money_dict[5] -= 3else:return False return True
406. 根據(jù)身高重建隊列
- 題目含義：原先的people是打亂順序，現(xiàn)在要重新排序得到queue
- 思路：首先對people進(jìn)行排序，先按照身高降序排序，身高相同時根據(jù) ki 進(jìn)行升序排列，這里key的傳參很妙；然后構(gòu)建新的隊列，插入的思想，以kj為依據(jù)進(jìn)行插入，實現(xiàn)同樣身高的，ki小的排在前面
- insert（索引值，插入的元素）
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)result = 2 ** 31 - 1sum_, i = 0, 0for j in range(n):sum_ += nums[j]while sum_ >= target:result = min(result, j - i + 1)sum_ -= nums[i]i += 1if result == 2**31 -1:return 0else:return result
452. 用最少數(shù)量的箭引爆氣球
- 思路：重疊的氣球都一起射 -> 記錄和更新重疊區(qū)間。point根據(jù)初始位置進(jìn)行排序，如果新位置不在重疊區(qū)間內(nèi)，則增加次數(shù)，更新重疊區(qū)間
class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key = lambda x: x[0])times = 1sl, sr = points[0][0], points[0][1]for i in range(1, len(points)):if points[i][0] > sr:times += 1sl, sr = points[i][0], points[i][1]sl, sr = max(sl, points[i][0]), min(sr, points[i][1])return times