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: n=len(ratings) nums=[1]*n for i in range(n-1): if ratings[i]>ratings[i+1]: nums[i]+=1 elif ratings[i]<ratings[i+1]: nums[i+1]+=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[i+1]: nums[i] = max(nums[i], nums[i+1] + 1) return sum(nums)860.柠檬水找零
题目链接860. 柠檬水找零 - 力扣（LeetCode）
思路
这个题还是可以理解，但是怎么做
如果现实生活让我给找零钱，就直接给
能不能维护一个数组就是我现在手上有的钱，然后一个一个加入，判断是否可以找零
class Solution: def lemonadeChange(self, bills: List[int]) -> bool: n=len(bills) nums=[] for i in range(n): if bills[i]==5: nums.append(bills[i]) elif bills[i]==10: count5=nums.count(5) if count5<1: return False else: nums.remove(5) nums.append(10) else: count5=nums.count(5) count10=nums.count(10) if count5>=3: nums.remove(5) nums.remove(5) nums.remove(5) nums.append(20) elif count10>=1 and count5>=1: nums.remove(10) nums.remove(5) nums.append(20) else: return False return True通过了55个样例，还是写的有点复杂
思路：
只需要记录 5 美元、10 美元的数量：
收到 5 美元：不用找零，5 的数量 +1
收到 10 美元：必须找 5 美元，5 的数量 -1，10 +1
收到 20 美元：优先找 10+5，没有再找 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美元 # 优先用 10+5 找零（贪心） 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(key=lambda x: (-x[0], x[1])) res = [] # 按 k 的位置插入 for p in people: res.insert(p[1], p) return res
