先看一个热身题目
55. 跳跃游戏
def canJump(self, nums: List[int]) -> bool:
l,reach = len(nums),0
for i in range(l):
if i > reach: return False
reach = max(reach, i + nums[i])
return True
1024. 视频拼接
这个贪心有点难。。。
def videoStitching(self, clips: List[List[int]], T: int) -> int:
#对于一个数字i,如果要覆盖到这个数字的后面一个数字，
#需要一个区间，区间左侧小于等于i,区间右侧大于等于i
#但是如果右侧只是等于i的话，只能覆盖到i,i后面的段就无法覆盖
#maxn表示左侧为clips[i][0]时能到达的最远右侧，这一步其实只是去重而已
maxn = [0] * T
for a, b in clips:
if a < T:
maxn[a] = max(maxn[a], b)
last = ret = pre = 0
for i in range(T):
#last表示 从i出发能覆盖到的最远右侧 和 当前能达到的最远右侧 中的 最大值
last = max(last, maxn[i])
#如果只能到达i,那么下一个位置无法被覆盖
#我们的循环范围是从i到T-1,要保证循环到T-1时,T可以被覆盖
if i == last:
return -1
#pre表示上一次还没有用完的最右边界
#当i==pre时,表示上一段空间用完了,ret表示最后需要的空间段数量
#这时ret+1,同时pre表示新的空间段的最右侧
if i == pre:
ret += 1
pre = last
print('i={},last={},pre={},ret={}'.format(i,last,pre,ret))
return ret
#example
#arr=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]] T=10
#stdout:
#i=0,last=2,pre=2,ret=1
#i=1,last=9,pre=2,ret=1
#i=2,last=9,pre=9,ret=2
#i=3,last=9,pre=9,ret=2
#i=4,last=9,pre=9,ret=2
#i=5,last=9,pre=9,ret=2
#i=6,last=9,pre=9,ret=2
#i=7,last=9,pre=9,ret=2
#i=8,last=10,pre=9,ret=2
#i=9,last=10,pre=10,ret=3
4.1520. 最多的不重叠子字符串
这个题目就不写代码了，具体看下思路
26个英文字母，把包含每个字母的最短串都求出来
然后用尽量多的子串去覆盖原来的字符串，且两两不重合，这就是一个典型的贪心问题
3 452. 用最少数量的箭引爆气球
之前阿里在线测评的时候碰到的一个问题，贪心算法，如何贪心？？
贪心算法一般用来解决需要 “找到要做某事的最小数量” 或 “找到在某些情况下适合的最大物品数量” 的问题，且提供的是无序的输入。
贪心算法的思想是每一步都选择最佳解决方案，最终获得全局最佳的解决方案。
标准解决方案具有 \mathcal{O}(N \log N)O(NlogN) 的时间复杂度且由以下两部分组成：
思考如何排序输入数据（\mathcal{O}(N \log N)O(NlogN) 的时间复杂度）。
思考如何解析排序后的数据（\mathcal{O}(N)O(N) 的时间复杂度
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x:x[1])
arrow = 1
current_end = points[0][1]
for x_start,x_end in points:
if x_start > current_end:
arrow += 1
current_end = x_end
return arrow
