代码随想录算法训练营 Day 25

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        sum_gas = sum(gas)
        sum_cost = sum(cost)

        if sum_cost > sum_gas:
            return -1
        
        curr_gas = 0
        idx = 0
        for i in range(len(gas)):
            curr_gas += gas[i] - cost[i]
            if curr_gas < 0:
                # 当前所累积的gas不足以满足从idx位置出发到当前位置
                curr_gas = 0
                idx = i + 1
        
        return idx

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curr_sum = 0
        min_tank = float('inf')

        for i in range(len(gas)):
            curr_sum += gas[i] - cost[i]
            if curr_sum < min_tank:
                min_tank = curr_sum
        
        # 第一种情况，开销大于补充，无法完成一圈
        if curr_sum < 0:
            return -1
        
        # 第二种情况，油箱里面一直剩的油，可以从0开始
        if min_tank > 0:
            return 0
        
        # 第三种情况，找到一个位置，使得从该位置出发，油箱剩余不会小于0
        for i in range(len(gas) - 1, -1, -1):
            min_tank += gas[i] - cost[i]
            if min_tank >= 0:
                return i

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)

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0
        ten = 0

        for cash in bills:
            if cash == 5:
                five += 1
            elif cash == 10:
                if five:
                    five -= 1
                    ten += 1
                else:
                    return False
            else:
                if ten:
                    ten -=1
                    cash -=10
                
                while cash > 5:
                    cash -= 5
                    five -= 1
                
                if five < 0:
                    return False
        
        return True

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

        res = []

        for p in people:
            res.insert(p[1], p)

        return res

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

        pos = list(range(len(people)))
        
        res = [0] * len(people)
        prev = None
        c = 0

        for p in people:
            if prev is not None and p[0] == prev:
                c += 1
                idx = p[1] - c
            else:
                idx = p[1]
                prev = p[0]
                c = 0
            idx = pos.pop(idx)
            res[idx] = p
        
        return res