day25-数据结构力扣

134. 加油站题目链接134. 加油站 - 力扣LeetCode思路虽然这个题看起来有点抽象但是你仔细看一下他的示例其实能明白设每一站的净油量diff[i] gas[i] - cost[i]总判断如果所有diff加起来 0 →总油不够跑一圈直接返回 -1。贪心找起点从某个起点出发一路累加油箱油量一旦油箱 0→ 说明从当前起点到这一站所有点都不能做起点→ 直接把起点换成下一站油箱清空重新算题目保证有解就唯一最后剩下的起点就是答案。提交total 整个旅途总共带的油够不够全程消耗不够 → 直接放弃curr 你现在车里还有多少油半路没油了 → 换个起点重新开from typing import List class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: n len(gas) total 0 # 总净油量判断能否跑完一圈 curr 0 # 当前油箱油量 start 0 # 记录起点 for i in range(n): diff gas[i] - cost[i] total diff curr diff # 当前油不够说明 [start, i] 都不能做起点 if curr 0: start i 1 # 起点换成下一站 curr 0 # 油箱清空 # 总油 0 才有解否则 -1 return start if total 0 else -1135. 分发糖果题目链接135. 分发糖果 - 力扣LeetCode思路class Solution: def candy(self, ratings: List[int]) - int: nlen(ratings) nums[1]*n for i in range(n-1): if ratings[i]ratings[i1]: nums[i]1 elif ratings[i]ratings[i1]: nums[i1]1 else: continue return sum(nums)我是这样写的代码但是题解说要两次遍历我完全理解不了通过18个用例纯没事找事这个题思路只遍历一次只能处理 “一对邻居”但题目需要 “连续一串” 都满足规则。我知道遍历一次是错的但是为什么要遍历两次还是不太懂要满足左右两边都要比必须遍历两次第一次左 → 右只保证如果右边 左边→ 右边糖果 左边糖果 1第二次右 → 左只保证如果左边 右边→ 左边糖果 右边糖果 1最后每个位置取最大值这样左右两边的规则都满足。提交class Solution: def candy(self, ratings: List[int]) - int: n len(ratings) nums [1] * n # 每人至少1颗 # 左→右保证右边 左边时糖更多 for i in range(1, n): if ratings[i] ratings[i-1]: nums[i] nums[i-1] 1 # 右→左保证左边 右边时糖更多 for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: nums[i] max(nums[i], nums[i1] 1) return sum(nums)860.柠檬水找零题目链接860. 柠檬水找零 - 力扣LeetCode思路这个题还是可以理解但是怎么做如果现实生活让我给找零钱就直接给能不能维护一个数组就是我现在手上有的钱然后一个一个加入判断是否可以找零class Solution: def lemonadeChange(self, bills: List[int]) - bool: nlen(bills) nums[] for i in range(n): if bills[i]5: nums.append(bills[i]) elif bills[i]10: count5nums.count(5) if count51: return False else: nums.remove(5) nums.append(10) else: count5nums.count(5) count10nums.count(10) if count53: nums.remove(5) nums.remove(5) nums.remove(5) nums.append(20) elif count101 and count51: nums.remove(10) nums.remove(5) nums.append(20) else: return False return True通过了55个样例还是写的有点复杂思路只需要记录 5 美元、10 美元的数量收到 5 美元不用找零5 的数量 1收到 10 美元必须找 5 美元5 的数量 -110 1收到 20 美元优先找 105没有再找 3 张 5因为 5 美元更通用要省着用任何一步找不开 → 直接 return False提交from typing import List class Solution: def lemonadeChange(self, bills: List[int]) - bool: five 0 # 只记5美元数量 ten 0 # 只记10美元数量 for bill in bills: if bill 5: five 1 elif bill 10: if five 0: # 必须找5美元 return False five - 1 ten 1 else: # 20美元 # 优先用 105 找零贪心 if ten 0 and five 0: ten - 1 five - 1 elif five 3: # 不行再用3张5 five - 3 else: # 都不行 return False return True406.根据身高重建队列题目链接406. 根据身高重建队列 - 力扣LeetCode思路怎么说光是看题就消耗了很多力气排序规则身高高的排前面降序身高一样k 小的排前面升序构造规则按排好的顺序把每个人插入到结果的第 k 个位置因为高的人已经先放好了矮的人插进去不会影响别人的 k 值高的人先放好后面插入矮个子不会改变高个子的 k 值矮个子直接插到第 k 位前面正好有 k 个比他高 / 等高的人提交from typing import List class Solution: def reconstructQueue(self, people: List[List[int]]) - List[List[int]]: # 排序身高从高到低身高相同 k 小的在前 people.sort(keylambda x: (-x[0], x[1])) res [] # 按 k 的位置插入 for p in people: res.insert(p[1], p) return res