來自leetcode題目：55，406，621

55.跳躍游戲

• 題目描述

  • 給定一個非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。
    數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
    判斷你是否能夠到達(dá)最后一個位置。

• 示例

  
  
  image.png

• 題解

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        '''
        盡可能到達(dá)最遠(yuǎn)位置(貪心算法)
        !!!如果能到達(dá)某個位置，就一定能到達(dá)它前面的所有位置
        初始化最遠(yuǎn)位置為0，遍歷數(shù)組，如果當(dāng)前位置能夠到達(dá)
        并且當(dāng)前位置+跳數(shù)>最遠(yuǎn)位置，就更新最遠(yuǎn)位置
        最后比較最遠(yuǎn)位置與數(shù)組長度即可
        '''
        max_i = 0
        #i為當(dāng)前位置，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.根據(jù)身高重建隊(duì)列

• 題目描述
  • 假設(shè)有打亂順序的一群人站成一個隊(duì)列。 每個人由一個整數(shù)對(h, k)表示，其中h是這個人的身高，k是排在這個人前面且身高大于或等于h的人數(shù)。 編寫一個算法來重建這個隊(duì)列。
    注意：
    總?cè)藬?shù)少于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.任務(wù)調(diào)度器

• 題目描述
  • 給定一個用字符數(shù)組表示的 CPU 需要執(zhí)行的任務(wù)列表。其中包含使用大寫的 A - Z 字母表示的26 種不同種類的任務(wù)。任務(wù)可以以任意順序執(zhí)行，并且每個任務(wù)都可以在 1 個單位時間內(nèi)執(zhí)行完。CPU 在任何一個單位時間內(nèi)都可以執(zhí)行一個任務(wù)，或者在待命狀態(tài)。
    然而，兩個相同種類的任務(wù)之間必須有長度為 n 的冷卻時間，因此至少有連續(xù) n 個單位時間內(nèi) CPU 在執(zhí)行不同的任務(wù)，或者在待命狀態(tài)。
    你需要計(jì)算完成所有任務(wù)所需要的最短時間。

• 示例

輸入：tasks = ["A","A","A","B","B","B"], n = 2
輸出：8
解釋：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，兩個相同類型任務(wù)之間必須間隔長度為 n = 2 的冷卻時間，而執(zhí)行一個任務(wù)只需要一個單位時間，所以中間出現(xiàn)了（待命）狀態(tài)。

• 題解

from collections import Counter
'''
題解：
桶思想： 桶大小為n+1，即相同任務(wù)不能放入同一個桶
桶的個數(shù)就是重復(fù)最多的任務(wù)的次數(shù)
除最后一個桶，其余桶所需的時間均為n+1
最后一個桶需要的時間為桶內(nèi)的任務(wù)個數(shù)
總時間=(桶個數(shù)-1)*(n+1)+最后一個桶的任務(wù)數(shù)
但是當(dāng)任務(wù)重復(fù)率很低，而任務(wù)很多時，可能桶的大小不夠，可以擴(kuò)展原有的桶
即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))