【Python刷题Leetcode】贪心算法（分糖果、摇摆序列、移除K个数、跳跃游戏、射击气球、加油次数）

排序，遍历糖果（糖果id++），若满足当前孩子，孩子id++。最终孩子id就是满足的孩子数。

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 每个孩子需求/饼干大小从小到大排序
        child = sorted(g)
        food = sorted(s)

        child_idx = 0
        food_idx = 0

        # 解法1：遍历糖果 用糖果满足孩子 最终的child_idx就是孩子数
        while child_idx < len(child) and food_idx < len(food):
            if child[child_idx] <= food[food_idx]:
                child_idx += 1
            food_idx += 1

        return child_idx
        
        # 解法2：遍历孩子 让孩子选最小可满足的糖果
        # count = 0
        # for ch in child:
        #     while food_idx < len(food):
        #         if food[food_idx]>=ch:
        #             count += 1
        #             food_idx += 1
        #             break
        #         food_idx += 1
        # 
        # return count

 

from collections import deque

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:

        # 对于1432219 从最高位1->最低位9
        S = deque() # 模拟栈

        for cur_num in num:
            cur_num = int(cur_num)

            # [栈非空] 且 [栈顶比当前值大] 且 [没删完]
            while len(S) and S[-1]>cur_num and k>0:
                S.pop() # 删之
                k -= 1  # 名额-1
            
            # 栈非空 或者 栈空但cur_name不是0
            if cur_num!=0 or len(S):  
                S.append(cur_num)

        # 处理完成后 如果[栈还不空]且[还没删完]
        while len(S) and k>0:
            S.pop()
            k-=1
        
        # 根据栈中元素
        res = ''.join([str(_) for _ in S]) if len(S) else '0'
        return res

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # i     = [0,1,2,3,4]   下标
        # nums  = [2,3,1,1,4]   最多可跳长度的数组
        # index = [2,4,3,4,8]   最远可跳位置的数组

        index = [i+nums[i] for i in range(len(nums))]  # 最远可跳至的位置
        jump = 0  # 扫描指针 指示当前位置
        max_index = index[0]

        while jump<len(nums) and jump<=max_index:
            # 如果可以跳的更远 就更新max_index
            if max_index<index[jump]:
                max_index = index[jump]
            print('当前在第%d个位置, 最远跳到%d' % (jump, max_index))

            jump += 1
        
        if jump == len(nums):
            return True
        return False

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)<2:
            return 0
        
        cur_max_index = nums[0]  # 当前可达的最远位置
        pre_max_index = nums[0]  # 遍历各个位置过程中 可达到的最远位置
        jump_min = 1

        for i in range(len(nums)):
            if i>cur_max_index:  # 当前位置超出了可达最远位置
                 jump_min+=1     # 跳步
                 cur_max_index=pre_max_index  # 更新当前可达最远位置
            if pre_max_index < nums[i]+i:
                pre_max_index=nums[i]+i
        
        return jump_min

注意[1,2] [2,3] [3,4] [4,5] 的情况，结果为2。

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        
        if not len(points):
            return 0

        # 根据X_start排序
        points = sorted(points)
        shooter = 1
        
        left = points[0][0]
        right = points[0][1]

        for ball in points:

            if ball[0] <= right: 
            # 如果当前球的左端比right还要小 那缩小范围 更新left和right
                left = ball[0]
                right = min(right, ball[1])
                continue

            # 否则把当前球更新为left和right 并加一shooter
            else:
                left = ball[0]
                right = ball[1]
                shooter += 1
        
        return shooter

 

import heapq

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:

        Q = []      # 大根堆 用来存加油站油量
        result = 0  # 记录加过几次油
        cur_fuel = startFuel  # 当前车里剩余油量 
        stations.append([target, 0])  # 把终点也当停靠点
        go_road = 0  # 走过了多少路
        print(stations)

        # 遍历加油站stations
        for station in stations:
            dis = station[0] - go_road # 从上个加油站到达该加油站的路程

            # 油量不够了(要加油) 且 最大堆不为空时(能加油)
            while cur_fuel<dis and len(Q):
                cur_fuel += -heapq.heappop(Q) # 加油
                result += 1
            
            # 还没到终点 但已经没油可加了
            if cur_fuel<dis and not len(Q):
                return -1
            
            # 前进到下个加油站 更新油量
            cur_fuel -= dis
            go_road += dis
            heapq.heappush(Q, -station[1])

        return result

 

本文地址：https://blog.csdn.net/muyao987/article/details/107311947