代码随想录算法训练营第31天 | 贪心3：134.加油站、135.分发糖果、860.柠檬水找零、406.根据身高重建队列

134.加油站
https://leetcode.cn/problems/gas-station/description/
代码随想录
https://programmercarl.com/0134.加油站.html
135.分发糖果
https://leetcode.cn/problems/candy/description/
代码随想录
https://programmercarl.com/0135.分发糖果.html
860.柠檬水找零
https://leetcode.cn/problems/lemonade-change/description/
代码随想录
https://programmercarl.com/0860.柠檬水找零.html
406.根据身高重建队列
https://leetcode.cn/problems/queue-reconstruction-by-height/
代码随想录
https://programmercarl.com/0406.根据身高重建队列.html

134.加油站

题解思路

• 局部优化：从0开始 如果最后的邮费小于0 说明能走完；
• 选择开始的加油站：如果 currsum<0 归零开始选择；

题解代码

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        currsum,finalsum,index = 0,0,0
        for i in range(len(gas)):
            data = gas[i]-cost[i]
            currsum += data
            finalsum += data
            if currsum<0:
                ### 当前油不够用 从下一个开始
                currsum = 0
                index = i+1
        ###判断是否能行走完
        if finalsum<0:
            return -1
        return index

135. 分发糖果

题解思路

• 需求分开
• 先从前往后比
• 再从后往前比

题解代码

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candy = [1]*len(ratings)
        for i in range(1,len(ratings)):## 都和前面的比
            if ratings[i]>ratings[i-1] and candy[i]<=candy[i-1]:
                candy[i] = candy[i-1]+1
        for j in range(len(ratings)-2,-1,-1):## 都和后面的比
            if ratings[j]>ratings[j+1] and candy[j]<=candy[j+1]:
                candy[j] = candy[j+1]+1
        return sum(candy)

860.柠檬水找零

题解思路

• 模拟纸钞技术

题解代码

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        back = {
            5:0,10:0,20:0
        }
        for i in range(len(bills)):
            if bills[i]==5:
                back[5]+=1
            elif bills[i]==10:
                if back[5]<1:
                    return False
                back[10]+=1
                back[5]-=1
            else:
                back[20]+=1
                if back[10]>0 and back[5]>0:
                    back[5]-=1
                    back[10]-=1
                elif back[5]>2:
                    back[5]-=3
                else:
                    return False
        return True

406.根据身高重建队列

题解思路

• 首先按照身高排序
• 按照前面的数字插入数字

题解代码

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 people:
            res.insert(i[1],i)
        return res