小工具知识网

当前位置: 首页 > 行业知识 > leetcode刷题之贪心算法

行业知识

leetcode刷题之贪心算法

2026-11-16 13:33:31 来源:互联网转载

455.分发饼干

()

��设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

()
class Solution(object):    def findContentChildren(self, g, s):        gi = 0        si = 0        g.sort()        s.sort()        while gi = g[gi]:                gi += 1            si += 1        return gi

435.无重叠区间

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。

class Solution(object):    def eraseOverlapIntervals(self, intervals):         # 对intervals列表按照每个子列表的第一个元素进行排序        intervals.sort(key=lambda x: x[0])        result = 0        # 遍历每一个子列表        for i in range(1,len(intervals)):            pre = intervals[i-1]            cur = intervals[i]            # cur左端点的值大于pre右端点的值 则证明不重合            if cur[0]  

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

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

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

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

class Solution(object):    def findMinArrowShots(self, points):        points.sort(key = lambda x:x[0])        result = 0        for i in range (1, len(points)):            pre = points[i-1]            cur = points[i]            if cur[0]  0:                profit += tmp        return profit

605. 种花问题

假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会***去。

给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示种植了花。另有一个数 n ,能否在不打破种植规则的情况下种入 n 朵花?能则返回 true ,不能则返回 false 。

class Solution(object):    def canPlaceFlowers(self, flowerbed, n):        # 若当前地的前面和后面都为0,则该地可以种花        # 考虑边界问题 最前面和最后面赋值为0        count = 0        flowerbed.insert(0,0)        flowerbed.append(0)        for i in range(1,len(flowerbed)-1):            if flowerbed[i]==0 and flowerbed[i-1]==0 and flowerbed[i+1]==0:                flowerbed[i] = 1 # 要先标记此处种花                i += 2 #该位置可以种花 则下个位置肯定不能种花 直接跳到下下个位置进行判断                count += 1                            else:                i += 1        return count>=n

392. 判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

class Solution(object):    def isSubsequence(self, s, t):        i = j = 0        slen = len(s)        tlen = len(t)        while i  

655.非递减数列

给你一个长度为 n 的整数数组 nums ,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。

class Solution(object):    def checkPossibility(self, num):        N = len(num)        count = 0        for i in range(1, N):           if num[i-1] > num[i]:               count += 1               # num[i-2] > num[i] 这种情况需要 num[i] = num[i-1]               # 相反的话 num[i-2] 

上一篇:QQ消息漫游功能揭秘,轻松实现聊天记录跨平台同步!

下一篇:如何下载并安装电脑应用商店