力扣视频拼接
视频拼接
题目:
示例:
思路:
这是今天上午力扣竞赛题的第四道,可能很多人看题的第一眼觉得要用贪心算法,但是怎么用,数据多的时候怎么找,怎么把时间复杂度减下去?这些都是挡在面前的大山。
我一开始也是有点迷,但是我看了示例,一个想法突然蹦到了我脑子里,既然这个题是贪心算法,我之前做过leetcode上另一道贪心算法的题,我能不能用那一道题的贪心算法?因为那一道题的贪心算法和这道题很像,那一道题是跳的最少步数,这道题是需要的最少片段数。
于是,大概的思路就有了:根据题意,我们一开始肯定要从0开始剪辑,我们如果要最少的片段,那么第一段肯定要尽可能的长,比如[0,3]和[0,5],那我们肯定要选择[0,5]这一段;接下来怎么剪辑呢?那肯定是从5开始剪辑或者从4,3,2,1开始剪辑(因为万一后四种片段更长呢?如[5,6]和[3,10],我们肯定要选后者,从3开始剪辑)…这样一来,贪心算法的结构就有了。
我们再处理另一个问题:如何从许多数据中找到我们所选片段的末尾(视频段结束的时间点),怎么减少复杂度呢?可以看出我们每一步都是找视频段最长的点,那我们的原数据可以用字典保存,每一个键我们都保存其对应的最大值,比如:[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]可以保存为{0:2,1:9,4:6,5:9,8:10}。这里所有键所对应的值都是原数据中最大的值。
原数据采用字典保存的原因及贪心算法细节:
还是上述例子,借用字典进行分析,num=0计数,T=10
- 我们首先从0开始找片段,num+1,我们发现我们最多可以剪辑到2,2不大于T,所以继续下面的步骤,否则我们直接返回num;
- 因为有可能从1处跳的更远,所以接下来我们看我们从(2,1)中开始剪辑最多能剪辑到哪里,通过查询字典,我们发现只能从1处开始剪辑(此过程中要判断剪辑段末尾时间是否超过T,超过则返回,不超过则计数+1并继续),可以看到1对应9,9不大于T,所以我们继续寻找,也就是我们可以从(9,8,7,6,5,4,3)中找下一个剪辑最远的点;
- 看从(9,8,7,6,5,4,3)这些剪辑点中哪个点剪辑能剪辑最远(若这些点都不存在字典的键中那么就可以直接返回-1了),我们找到这个能剪辑的最远点,我们从这个点出发,再次进行上述步骤。 这里我们发现找到8点的时候,我们就能剪辑到10了,所以此时我们返回num,num=3。
代码:
class Solution:
def videoStitching(self, clips: List[List[int]], T: int) -> int:
res={}
if T==0:return 0
#将原数据保存在字典中
for i in range(len(clips)):
if clips[i][0] not in res:
res[clips[i][0]]=clips[i][1]
else:
#保存某点能剪辑到的最远处值
res[clips[i][0]]=max(clips[i][1],res[clips[i][0]])
if 0 not in res:return -1
#num用来计数
i=num=0
while i<=T:
num+=1
#如果我们从这个点直接就剪辑到T处,就返回num
if res[i]>=T:return num
#此处k是为了确定我们能在哪个范围内找剪辑点,k是剪辑范围最小值
k=i
#这里base是为了找到能跳的最远的点,j是剪辑范围的最大值
base=j=res[i]
#针对剪辑中间缺少的情况设置,即如果给的原数据就不在那个范围内,就可以返回-1了
z=0
while j>k:
if j in res and res[j]>base:
z=1
base=res[j]
#更新剪辑最远的下标处
i=j
j-=1
#依然是判断该剪辑点是否剪辑超过T
if res[i]>=T:return num+1
#若视频缺少,返回-1
if z==0:return -1