860. 檸檬水找零

在檸檬水攤上，每一杯檸檬水的售價為?5?美元。顧客排隊購買你的產(chǎn)品，（按賬單 bills 支付的順序）一次購買一杯。

每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。

注意，一開始你手頭沒有任何零錢。

給你一個整數(shù)數(shù)組 bills ，其中 bills[i] 是第 i 位顧客付的賬。如果你能給每位顧客正確找零，返回?true?，否則返回 false?。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/lemonade-change
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        # 分別對應 5、10、15
        changes = [0,0,0]
        for i in range(len(bills)):
            if bills[i]== 5:
                changes[0]+=1
            elif bills[i]==10:
                if changes[0]>=1:
                    changes[0]-=1
                    changes[1]+=1
                else:
                    return False
            else:
                if changes[0] >=1 and changes[1]>=1:
                    changes[0]-=1
                    changes[1]-=1
                elif changes[0]>=3:
                    changes[0]-=3
                else:
                    return False
        return True

406. 根據(jù)身高重建隊列

假設有打亂順序的一群人站成一個隊列，數(shù)組 people 表示隊列中一些人的屬性（不一定按順序）。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人。

請你重新構造并返回輸入數(shù)組?people 所表示的隊列。返回的隊列應該格式化為數(shù)組 queue ，其中 queue[j] = [hj, kj] 是隊列中第 j 個人的屬性（queue[0] 是排在隊列前面的人）。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/queue-reconstruction-by-height
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

局部最優(yōu)：優(yōu)先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性

全局最優(yōu)：最后都做完插入操作，整個隊列滿足題目隊列屬性

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 先按照h維度的身高順序從高到低排序確定第一個維度
        # lambda返回的是一個元組，當-x[0](維度h)相同時，
        # 再根據(jù)x[1](維度k)從小到大排序
        people.sort(key = lambda x : (-x[0],x[1]))
        que = []
        # 根據(jù)每個元素的第二個維度k，貪心算法,進行插入
        for p in people:
            que.insert(p[1],p)
        return que

452. 用最少數(shù)量的箭引爆氣球

有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數(shù)數(shù)組?points?，其中points[i] = [xstart, xend]?表示水平直徑在?xstart?和?xend之間的氣球。你不知道氣球的確切 y 坐標。

一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 ?xstart?≤ x ≤ xend，則該氣球會被 引爆??？梢陨涑龅墓臄?shù)量 沒有限制 。 弓箭一旦被射出之后，可以無限地前進。

給你一個數(shù)組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數(shù)?。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。文章來源地址http://www.zghlxwxcb.cn/news/detail-524794.html

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points)==0:
            return 0
        # 以左邊界排序
        points.sort(key=lambda x:x[0])
        result = 1
        for i in range(1,len(points)):
            # 如果當前氣球左邊界大于上一個氣球的右邊界
            if points[i][0] > points[i-1][1]:
                result +=1
            else: # 重疊情況
            # 更新重疊氣球最小右邊界
                points[i][1] = min(points[i][1],points[i-1][1])
        return result

到了這里，關于Python版day35的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！