10.24
LeetCode 每日一题 1024.视频拼接
题目分析：
题目要求我们从几个视频片段中，找出能够组成0~T这段时间的完整视频！每一段视频也都支持裁剪，最后需要我们求出，用最少的片段组 成这一段完整的视频！
方法一： 动态规划
此系列问题，基本都可以用动态规划求解，动态规划求解问题，最难的地方就是找出状态方程式。我们根据题目的意思思考，我们最后需要得到的片段就是[0~T]这个片段，那么这个片段我们可以怎么表示呢？我们可以用一个dp数组，令dp[i]表示从0~i这个片段所需要的最小片段数。依次自底向上，最后得到dp[T]即为我们想要得到的结果。
但是有一点就是，dp[i]的初始值的问题，因为题目想要的是尽可能得到更少的子片段去组成一个完整的片段，所以我们把dp[i]初始化为一个比较大的整数，然后特殊的是dp[0]要初始化为0，相信大家应该也都能理解。
说到这里，我们上面将返回的结果转化为用一个dp数组去储存，最后只需要返回即可。那么我们要怎么去求出每一个dp[i]呢？很明显这个时候就需要用到循环了，从1开始遍历，遍历到最大时间T，依次算出每一个dp[i]。
重点来了，我们知道dp[i]代表从0~i这个片段需要最小的片段数，所以每一次符合条件的片段都必须满足**clip[0] < i <= clip[1]**这一条件，用文字叙述就是说，满足的这一子片段的起点必须比所需要的完整片段的终点小，终点必须大于或者等于完整片段的终点。这样才能够构成完整片段。所以此时我们就可以这么转化，我们在之前所说的自底向上就在这里体现了，我们想要求得dp[i]，则可以转化为求以当前符合要求的子片段的起点为终点的完整片段，加上这一个子片段，这一就能够得到dp[i]的值了。即 dp[i] = dp[clip[0]] + 1，由于我们每次都要得到最小的片段数目，此时dp[i]就需要取得最小的那个值，即最终的状态方程为 dp[i] = Math.max(dp[i], dp[clip[0]]+1)。
返回的结果，因为题目也说了，可能给出的这一片段不能构成一段完整的视频，此时就返回-1，若能构成则返回所需片段的最小数。所以我们的返回值可以用一个三目表达式来做。当 dp[T] 为最大值的时候，此时证明没有解，则返回-1，当有解的时候，dp[T]则不可能为最大值，则直接返回dp[T]。
下面直接给出代码：
public int videoStitching(int[][] clips, int T) {
int[] dp = new int[T+1];
Arrays.fill(dp,Integer.MAX_VALUE-1); // 每一个dp[i]都初始化为一个很大的值
dp[0] = 0;
for (int i = 1; i <= T; i++){
for (int[] clip:clips){ // 在所有片段中寻找
/*
clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
为了加强理解，在这里举个例子 当i为1的时候 此时 内层循环从上面的二维数组取出一个片段clip = {0,2}
此时片段的起点为0 终点为2,很明显 0<1<=2,此时证明了什么？ 0-2的这个片段可以裁剪出0-1这个片段
所以我们想要求dp[1]就可以转化为以0（clip[0]）为终点的片段，加上0-2这一片段。即 dp[1] = dp[0]+1
为什么要再来一个Math.min取较小的值呢？因为片段是从头往后遍历的，可能满足条件的片段很多，所以就需要取较小的值
*/
if (clip[0] < i && clip[1] >= i){
dp[i] = Math.min(dp[i],dp[clip[0]]+1);
}
}
}
return dp[T] == Integer.MAX_VALUE-1 ? -1:dp[T];
}
复杂度分析
时间复杂度： O(T×N)，其中 T 是完整片段的长度，N 是子片段的数量。
空间复杂度： O(T)，其中 T 是完整片段的长度。
方法二： 贪心法
题解思路：（借鉴了官方题解）
定义并初始化一个数组
max，max[i]表示从 以i为起点的片段的最大结束位置定义三个变量，
start表示当前的起点，end表示以start为起点能到达的最大终点，sum表示子片段数根据
max数组当前元素 == 本区间最大元素 end，
即：区间断开，无法连续到后续位置，返回-1当前元素 == 上一个区间的最大结束元素，即start
即：到达了上一个满足条件的区间的结束位置，此时片段数加一，下个片段起点为end
public int videoStitching(int[][] clips, int T) {
int[] max = new int[T];
for (int[]clip:clips){
if (clip[0]<T){
max[clip[0]] = Math.max(max[clip[0]],clip[1]);
}
}
int end = 0,sum = 0, start = 0;
for (int i = 0; i < T; i++){
end = Math.max(max[i],end);
if (i == end) // 当起点i 与 i能到达的最大位置相等时，则此时是无解的，因为片段断了
return -1;
if (i == start){
sum++;
start = end;
if (end == T) //找到完整的片段，提前结束，减少循环
break;
}
}
return sum;
}
复杂度分析
时间复杂度： O(T×N)，其中 T 是完整片段的长度，N 是子片段的数量。
空间复杂度： O(T)，其中 T 是完整片段的长度。