行业知识
leetcode刷题之贪心算法
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 profit605. 种花问题
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会***去。
给你一个整数数组 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>=n392. 判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
class Solution(object): def isSubsequence(self, s, t): i = j = 0 slen = len(s) tlen = len(t) while i655.非递减数列
给你一个长度为 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]