代码随想录算法训练营第三十九天(贪心算法篇)| 406. 根据身高重建队列, 452. 用最少数量的箭引爆气球

发布时间:2024年01月24日

406.根据身高重建队列

资料:代码随想录 (programmercarl.com)

题目大意:数组people表示队列中一些人的属性(不一定按顺序)。每个?people[i] = [hi, ki]?表示第?i?个人的身高为?hi?,前面?正好?有?ki?个身高大于或等于?hi?的人。返回数组queue,是?queue[j] = [hj, kj]?可以正确表示队列中第?j?个人的属性(queue[0]?是排在队列最前面的人)。

思路

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]],以[4,4]为例,它在queue中,前面有四个比它大或等于它的数组,但people中全部数组都满足这一点,所以不管其它数组的顺序如何,它一定在第四个。如果可以理解这个想法,其实稍加扩展就能得到完整的思路:找到比当前数组大的元素,根据它的k值插入它们当中。

题目涉及到两个维度,h和k,要先确定一个维度后,再根据第二个维度调整。先按k排列的无意义,因此先按照身高从大到小排列(如果身高相同,按照k从小到大),这样保证每一组前面的身高比它高。再根据每组的k,插入到queue中。从身高最高的开始插入,这样后序插入节点也不会影响前面已经插入的节点(因为前面已经插入的节点一定都比它高)。

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

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

Python基础语句

sort

对于一个嵌套数组,直接使用sort函数,会现根据数组元素第一个大小按顺序排,如果相同,在依次比较后一个。而对于这道题目,需要按第一个元素从大到小,相同情况下按第二个从小到大,可以借助lambda函数:

people.sort(key = lambda x:(-x[0], x[1]))

insert函数

queue.insert(order, item)
# order: 插在第几位  item:要插入的元素

代码实现

class Solution(object):
    def reconstructQueue(self, people):
        people.sort(key = lambda x:(-x[0], x[1]))
        queue = []
        for item in people:
            queue.insert(item[1], item)
        return queue

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

题目链接:452. 用最少数量的箭引爆气球 - 力扣(LeetCode)

题目大意

一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组?points?,其中points[i] = [xstart, xend]?表示水平直径在?xstart?和?xend之间的气球。不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点?完全垂直?地射出。在坐标?x?处射出一支箭,若有一个气球的直径的开始和结束坐标为?xstartxend,?且满足 ?xstart?≤ x ≤ xend,则该气球会被?引爆?。可以射出的弓箭的数量?没有限制?。 弓箭一旦被射出之后,可以无限地前进。

思路

如果两个区间有交集,可用一只箭引爆,多个气球最少需要的箭为总气球的数量减去交集的次数。先将数组从小到达排序,如果后一个的xstart在前一个的区间之间,则重叠,更新区间(取两个区间的交集),如果不重叠,新的区间为当前的points。也可以直接统计需要箭的数量,即如果后一个的xstart在上一个xend的右边,就加一支。

代码实现

class Solution(object):
    def findMinArrowShots(self, points):
        points.sort()
        interval = points[0]
        overclap = 0
        for i in range(1, len(points)):
            if points[i][0] <= interval[1] and points[i][0] >= interval[0]:
                overclap += 1
                interval[0] = points[i][0]
                interval[1] = min(points[i][1], interval[1])
            else:
                interval = points[i]
        return len(points) - overclap 
class Solution(object):
    def findMinArrowShots(self, points):
        points.sort()
        interval = points[0]
        bow = 1
        for i in range(1, len(points)):
            if points[i][0] > interval[1] :
                bow += 1
                interval[0], interval[1] = points[i][0], points[i][1]
            else:
                interval[0] =points[i][0]
                interval[1] = min(points[i][1], interval[1])
           
        return bow

35. 无重叠区间

题目链接:435. 无重叠区间 - 力扣(LeetCode)

思路

和上面“引爆气球”的思路很像,将intervals排序后,统计重叠次数,若重叠,取区间的交集(相当于留下范围小的区间,删掉范围大的,这样才能保证得到最小移除区间。),继续比较。

代码实现

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        space = intervals[0]
        num = 0
        for i in range(1, len(intervals)):
            if intervals[i][0] >= space[1]:
                space = intervals[i]
            else:
                num += 1
                space[1] = min(space[1], intervals[i][1])
        return num

也可以不用单独变量space,直接比较当前和前一个interval,看是否重叠。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort()  
        num = 0  
        
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:  # 存在重叠区间
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  
                num += 1
        
        return num

文章来源:https://blog.csdn.net/Huiwen18/article/details/135814685
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。