中等难度-贪心算法

来自leetcode题目：55，406，621

55.跳跃游戏

• 题目描述

  • 给定一个非负整数数组，你最初位于数组的第一个位置。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个位置。

• 示例

  
  
  image.png

• 题解

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        '''
        尽可能到达最远位置(贪心算法)
        !!!如果能到达某个位置，就一定能到达它前面的所有位置
        初始化最远位置为0，遍历数组，如果当前位置能够到达
        并且当前位置+跳数>最远位置，就更新最远位置
        最后比较最远位置与数组长度即可
        '''
        max_i = 0
        #i为当前位置，jump是能跳的最大距离
        for i,jump in enumerate(nums):
            if max_i >= i and i+jump > max_i:
                max_i = i + jump
        return max_i >= Ien(mums)

406.根据身高重建队列

• 题目描述
  • 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
    注意：
    总人数少于1100人
• 示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

• 题解

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 个子矮的人相对于个子高的人是不可见的
        # 先相对于h值降序排列，再相对于k值升序排列
        people.sort(key = lambda x: (-x[0], x[1]))
        output = []
        for p in people:
            output.insert(p[1], p)
        return output

621.任务调度器

• 题目描述
  • 给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
    然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
    你需要计算完成所有任务所需要的最短时间。

• 示例

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

• 题解

from collections import Counter
'''
题解：
桶思想： 桶大小为n+1，即相同任务不能放入同一个桶
桶的个数就是重复最多的任务的次数
除最后一个桶，其余桶所需的时间均为n+1
最后一个桶需要的时间为桶内的任务个数
总时间=(桶个数-1)*(n+1)+最后一个桶的任务数
但是当任务重复率很低，而任务很多时，可能桶的大小不够，可以扩展原有的桶
即tasks的长度就是所需的时间
'''
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        ct = Counter(tasks)
        nbucket = ct.most_common(1)[0][1]
        last_bucket_size = list(ct.values()).count(nbucket)
        res = (nbucket - 1) * (n + 1) + last_bucket_size
        return max(res, len(tasks))