Python版day35-Toy模板网

这篇具有很好参考价值的文章主要介绍了Python版day35。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lemonade-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/queue-reconstruction-by-height
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 先按照h维度的身高顺序从高到低排序确定第一个维度
        # lambda返回的是一个元组，当-x[0](维度h)相同时，
        # 再根据x[1](维度k)从小到大排序
        people.sort(key = lambda x : (-x[0],x[1]))
        que = []
        # 根据每个元素的第二个维度k，贪心算法,进行插入
        for p in people:
            que.insert(p[1],p)
        return que

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。文章来源地址https://www.toymoban.com/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的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！