您现在的位置是:首页 >技术教程 >算法记录 | Day35 贪心算法网站首页技术教程

算法记录 | Day35 贪心算法

是菜鸡小小陈啊 2023-05-23 00:00:02
简介算法记录 | Day35 贪心算法

860.柠檬水找零

思路:

只需要维护三种金额的数量,5,10和20。

有如下三种情况:

  • 情况一:账单是5,直接收下。
  • 情况二:账单是10,消耗一个5,增加一个10
  • 情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

账单是20的情况,优先消耗一个10和一个5

因为美元10只能给账单20找零,而美元5可以给账单10和账单20找零,美元5更万能!

所以局部最优:遇到账单20,优先消耗美元10,完成本次找零。全局最优:完成全部账单的找零。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0 
        ten = 0 
        twenty = 0
        for bill in bills:
            if bill == 5: five += 1
            if bill == 10: 
                if five < 0: return False
                ten += 1
                five -= 1
            if bill == 20:
                if ten > 0 and five > 0:
                    twenty += 1
                    ten -= 1
                    five -=1
                elif five >= 3:
                    twenty += 1
                    five -= 3
                else:
                    return False
        return True

406.根据身高重建队列

思路:

1.可以先确定身高维度。将数组按身高从高到低进行排序,身高相同的则按照 k值升序排列。这样排序之后可以确定目前对于第 j 个人来说,前面的 j - 1 个人肯定比他都高。

2.建立一个包含 n 个位置的空队列 queue,按照上边排好的顺序遍历,依次将其插入到第 kj位置上。最后返回新的队列。

406.根据身高重建队列

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0],x[1] ))
        que = []
        for p in people:
            que.insert(p[1],p)
        return que

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

思路:

按开始坐标升序排序需要考虑一种情况:有交集关系的区间中,有的区间结束位置比较早。比如 [0, 6] [1, 2] [4, 5]

,按照开始坐标升序排序的话,如下:

[0 . . . . . 6]
  [1 2]
        [4,5]

第一箭的位置需要进行迭代判断,取区间 [0, 6] [1, 2]中结束位置最小的位置,即arrow_pos = min(points[i][1], arrow_pos),然后再判断接下来的区间是否能够引爆。

而按照结束坐标排序的话,箭的位置一开始就确定了,不需要再改变和判断箭的位置,直接判断区间即可。

按开始位置排序

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:return False
        points.sort(key=lambda x:x[0])
        arow_pos = points[0][1]
        count = 1
        for i in range(len(points)):
            if arow_pos < points[i][0]:
                count += 1
                arow_pos = points[i][1]
            else:
                arow_pos = min(arow_pos, points[i][1])
        return count

按结束位置排序

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:return False
        points.sort(key=lambda x:x[1])
        arow_pos = points[0][1]
        count = 1
        for i in range(len(points)):
            if arow_pos < points[i][0]:
                count += 1
                arow_pos = points[i][1]
        return count
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。