您现在的位置是：首页 >技术教程 >代码随想录算法训练营第三十四天| 贪心算法03网站首页技术教程

134. 加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二

代码随想录

注意点：

1. 每一站加油量减去耗油量的总和小于0说明跑不完一圈

2. 当前站加油量减去耗油量小于0说明跑不到下一站，计数从下一站开始

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        cur_sum=0
        total_sum=0
        start=0
        for i in range(len(gas)):
            cur_sum+=gas[i]-cost[i]
            total_sum+=gas[i]-cost[i]
            if cur_sum<0:
                start=i+1
                cur_sum=0
        if total_sum<0:
            return -1
        return start

135. 分发糖果

本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路

代码随想录

注意点：

1. 从左到右，如果当前孩子评分比前一个高，则当前孩子的糖果数比前一个孩子多一个

2. 从右到左，如果当前孩子评分比后一个高，则当前孩子的糖果数取当前值和后一个孩子多一个值的最大值

3. 两个孩子评分一样的情况下，即便相邻，也可能分得的糖果不一样多

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n=len(ratings)
        candy=[1]*n
        for i in range(1,n):
            if ratings[i]>ratings[i-1]:
                candy[i]=candy[i-1]+1
        for i in range(n-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                candy[i]=max(candy[i],candy[i+1]+1)
        return sum(candy)

860. 柠檬水找零

本题看上好像挺难，其实很简单，大家先尝试自己做一做。

代码随想录

注意点：

对于20进行找零的情况，优先找一张10元和一张5元，如果没有十元再考虑找三张5元

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

460. 根据身高重建队列

本题有点难度，和分发糖果类似，不要两头兼顾，处理好一边再处理另一边。

代码随想录

1. people.sort(key=lambda x: (-x[0], x[1]))的意思是第一个元素降序排，若第一个元素一样大则第二个元素升序排，lambda返回的是一个元组

2. 按照每个人的ki值插入到队列中，list.insert(index, element)

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        queue=[]
        for p in people:
            queue.insert(p[1], p)
        return queue