关注Java领域相关技术 记录有趣的事情

LeetCode-1024. 视频拼接

US-B.Ralph
US-B.Ralph
2020-10-24

问题地址

LeetCode每日一题/2020-10-24

LeetCode1024. 视频拼接


问题描述

规则

你将会获得一系列视频片段,这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。

视频片段 clips[i] 都用区间进行表示:开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, T])。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。

示例

  • 示例1
输入:clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
输出:3
解释:
我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后,按下面的方案重制比赛片段:
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10],而这些涵盖了整场比赛 [0, 10]。
  • 示例2
输入:clips = [[0,1],[1,2]], T = 5
输出:-1
解释:
我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。
  • 示例3
输入:clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
输出:3
解释: 
我们选取片段 [0,4], [4,7] 和 [6,9] 。
  • 示例4
输入:clips = [[0,4],[2,8]], T = 5
输出:2
解释:
注意,你可能录制超过比赛结束时间的视频。

进阶

  • 1 <= clips.length <= 100
  • 0 <= clips[i][0] <= clips[i][1] <= 100
  • 0 <= T <= 100

思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现


官方解法

前言

本题要求从一系列视频子区间中选出尽可能少的一部分,使得这部分视频子区间能够重新剪出一个完整的视频。我们可以这样理解:给定区间 [0,T) 的一系列子区间(可能重叠),要求从中选出尽可能少的子区间,使得这些子区间能够完全覆盖区间 [0,T)。

为下文表述方便,我们用 [a,b) 来代表每一个子区间,第 i 个子区间表示为 [a_i,b_i)

方法一 动态规划

思路及算法

  • 比较容易想到的方法是动态规划,我们令 \textit{dp}[i] 表示将区间 [0,i) 覆盖所需的最少子区间的数量。由于我们希望子区间的数目尽可能少,因此可以将所有 \textit{dp}[i] 的初始值设为一个大整数,并将 \textit{dp}[0](即空区间)的初始值设为 0。

  • 我们可以枚举所有的子区间来依次计算出所有的 \textit{dp} 值。我们首先枚举 i,同时对于任意一个子区间 [a_j,b_j),若其满足d: a_j < i ≤ b_j 。

  • 那么它就可以覆盖区间 [0, i) 的后半部分,而前半部分则可以用 \textit{dp}[a_j] 对应的最优方法进行覆盖,因此我们可以用 dp[a_j] + 1 来更新 \textit{dp}[i]。状态转移方程如下:dp[i] = \min{dp[a_j]}+ 1

  • 最终的答案即为 \textit{dp}[T]

复杂度分析:

  1. 时间复杂度:O(T×N),其中 T 是区间的长度,N 是子区间的数量。对于任意一个前缀区间 [0,i) ,我们都需要枚举所有的子区间,时间复杂度 O(N)。总时间复杂度为 O(T) \times O(N) = O(T \times N)
  2. 空间复杂度:O(T),其中 T 是区间的长度。我们需要记录每一个前缀区间 [0,i) 的状态信息。

编码实现

class Solution {
    public int videoStitching(int[][] clips, int T) {
        int[] dp = new int[T + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        for (int i = 1; i <= T; i++) {
            for (int[] clip : clips) {
                if (clip[0] < i && i <= clip[1]) {
                    dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                }
            }
        }
        return dp[T] == Integer.MAX_VALUE - 1 ? -1 : dp[T];
    }
}

方法二 贪心

思路

  • 注意到对于所有左端点相同的子区间,其右端点越远越有利。且最佳方案中不可能出现两个左端点相同的子区间。于是我们预处理所有的子区间,对于每一个位置 i,我们记录以其为左端点的子区间中最远的右端点,记为 \textit{maxn}[i]
  • 我们可以参考「55. 跳跃游戏的官方题解」,使用贪心解决这道题。
  • 具体地,我们枚举每一个位置,假设当枚举到位置 i 时,记左端点不大于 i 的所有子区间的最远右端点为 \textit{last}。这样 \textit{last} 就代表了当前能覆盖到的最远的右端点。
  • 每次我们枚举到一个新位置,我们都用 \textit{maxn}[i] 来更新 \textit{last}。如果更新后 last == ilast==i,那么说明下一个位置无法被覆盖,我们无法完成目标。
  • 同时我们还需要记录上一个被使用的子区间的结束位置为 \textit{pre},每次我们越过一个被使用的子区间,就说明我们要启用一个新子区间,这个新子区间的结束位置即为当前的 \textit{last}。也就是说,每次我们遇到 i == pre,则说明我们用完了一个被使用的子区间。这种情况下我们让答案加 1,并更新 \textit{pre} 即可。

复杂度分析:

  1. 时间复杂度:O(T+N),其中 T 是区间的长度,N 是子区间的数量。我们都需要枚举每一个位置,时间复杂度 O(T)。总时间复杂度为 O(T) + O(N) = O(T + N)

  2. 空间复杂度:O(T),其中 T 是区间的长度。我们需要记录以其为左端点的子区间的最右端点。

编码实现

class Solution {
    public int videoStitching(int[][] clips, int T) {
        int[] maxn = new int[T];
        int last = 0, ret = 0, pre = 0;
        for (int[] clip : clips) {
            if (clip[0] < T) {
                maxn[clip[0]] = Math.max(maxn[clip[0]], clip[1]);
            }
        }
        for (int i = 0; i < T; i++) {
            last = Math.max(last, maxn[i]);
            if (i == last) {
                return -1;
            }
            if (i == pre) {
                ret++;
                pre = last;
            }
        }
        return ret;
    }
}

精彩评论

跳转地址1:【Java】1024节,不准不“贪心”

思路

(本题解 借鉴了 官方题解 的思想)
– 很纯粹的 贪心 思想:
– 1、首先来初始化一个 maxEnd数组,用于保存 以当前数字(下标)为起点 的区间的 最大的结束位置
– 2、遍历clips,初始化maxEnd数组(每个元素开头的区间的最大结束位置)
– 3、定义三个变量,辅助完成之后的操作:
– 1、pre 记录 结果中上一次的最大结束位置(本轮的最小开始位置)
– 2、last 记录 当前遍历到的 区间最大结束位置
– 3、count 记录 结果
– 4、根据maxEnd数组,计算最终结果

  • 因为maxEnd[i]数组为最大结束位置,因此:
    • 当前元素 == 本区间最大元素,即:区间断开,无法连续到后续位置,返回-1;
    • 当前元素 == 上一个区间的最大结束元素,即:到达了上一个满足条件的区间的结束位置
      这时的last为当前最大的结束位置,我们将其放入满足条件的区间集合之中(因为本题只需要我们记录 满足条件的区间个数,因为只需要 更新count和pre 即可)

编码实现

class Solution {
    public int videoStitching(int[][] clips, int T) {
        if (clips == null) {
            return 0;
        }

        int[] maxEnd = new int[T];  // 用于保存 以当前数字(下标)为起点 的区间的 最大的结束位置

        /*
            遍历clips,初始化maxEnd数组(每个元素开头的区间的最大结束位置)
         */
        for (int[] clip : clips) {
            if (clip[0] < T) {
                maxEnd[clip[0]] = Math.max(maxEnd[clip[0]], clip[1]);
            }
        }

        /*
            根据maxEnd数组,计算最终结果
                因为maxEnd[i]数组为最大结束位置,因此:
                    1、当前元素 == 本区间最大元素,
                        即:区间断开,无法连续到后续位置,返回-1
                    2、当前元素 == 上一个区间的最大结束元素,
                        即:到达了上一个满足条件的区间的结束位置
                        这时的last为当前最大的结束位置,我们将其放入满足条件的区间集合之中
                        (因为本题只需要我们记录 满足条件的区间个数,因为只需要 更新count和pre 即可)
         */
        int pre = 0;    // 记录 结果中上一次的最大结束位置(本轮的最小开始位置)
        int last = 0;   // 记录当前遍历到的 区间最大结束位置
        int count = 0; // 记录结果
        for (int i = 0; i < T; i++) {
            last = Math.max(maxEnd[i], last);
            if (i == last) {    // 当前元素 == 本区间最大元素(无法到达后续位置)
                return -1;
            }

            if (i == pre) { // 当前元素 == 上一个区间的最大元素
                count++;
                pre = last;
            }
        }
        return count;
    }
}
}

//反转链表
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

跳转地址2:「手画图解」动态规划 思路 | 分情况讨论

思路

题目要求覆盖[0,T]区间的最少片段数。

对于每个片段,用或不用,用就+1,且用过的片段,会影响之后对片段的选用,过去的状态影响当前状态,有 DP 的味道了。

尝试定义dp[j],表示:覆盖[0,j]区间的最少片段数,题目是求dp[T]。

先将片段按开始时间从小到大排序,满足DP「顺序计算」的特点,先遍历“靠前”的片段。做什么事情呢?计算每个片段里的所有dp[j]。

从左到右求,有些dp[j]可能会重复求(如上图),求出值更小,就更新。最后求出dp[T]。

  • 怎么求dp[j]?即,递推关系怎么找?我们画图看看,有哪些情况:
    • 情况1,覆盖不了[0:start],也覆盖不了[0:j],我们让dp[start]为一个很大的值,101,所有为101的 dp 结果都代表无法覆盖,返回 -1。此时dp[j]不小于 101 即可。
    • 情况2,覆盖[0:start]只要一个片段,覆盖[0:j],一个片段不够,还要加上它所在的片段,有dp[j]=dp[start]+1。
    • 情况3,之前计算过dp[j],再次计算,则要和之前的dp[j]比较,取较小者:dp[j]=min(dp[j], dp[start]+1)

回过头看情况1,dp[start]=101,我们希望dp[j]不小于101,且满足递推公式dp[j]=min(dp[j], dp[start]+1),于是我们让所有dp[j]初始值为101。这是 base case 之一。

回过头看情况2,如下图,dp[start]其实求了两次,第一次dp[start]怎么求?同样为了套用dp[j]=min(dp[j], dp[start]+1),让dp[0]=0,dp[start]初始为101,套公式为 min(101, 0+1)。

编码实现

递推公式有了,base case 有了,就可以写代码了。

const videoStitching = (clips, T) => {
  clips.sort((a, b) => a[0] - b[0]); // 按开始时间从小到大排序
  // dp[j]:涵盖[0:j]需要的clip的最少个数,目标是求dp[T],初始值为101,大于所有可能值
  const dp = new Array(T + 1).fill(101);
  dp[0] = 0;        // base case

  for (let i = 0; i < clips.length; i++) { // 遍历每个片段
    const [start, end] = clips[i];         // 获取当前片段的开始和结束时间
    for (let j = start + 1; j <= end; j++) { // 计算当前片段上每个点的dp[j]
      dp[j] = Math.min(dp[j], dp[start] + 1);
    }
  }
  if (dp[T] == 101) { // 如果dp值为101,说明覆盖不了[0:T],否则返回dp[T]
    return -1;
  }
  return dp[T];
};

总结复盘

动态规划顺序计算的特点决定了要排序。

过去的计算结果会影响到当前的计算,当前的计算,还受「当前所在片段的 start 的计算结果」的影响。

二者作用之下,写出递推公式(状态转移方程)。

然后 base case 基于公式往上套,让「边界情况也能套用上递推公式」而已。

大致的思路就是这样。

优化

当dp[start] = 101时,表示覆盖不了[0:start],肯定覆盖不了[0,j]的,没必要遍历当前片段[start:end]上的所有j,直接 break:

const videoStitching = (clips, T) => {
  clips.sort((a, b) => a[0] - b[0]); // 按开始时间从小到大排序
  // dp[j]:涵盖[0:j]需要的clip的最少个数,目标是求dp[T],初始值为101,大于所有可能值
  const dp = new Array(T + 1).fill(101);
  dp[0] = 0; // 涵盖[0:0]不需要clip,所以为0

  for (let i = 0; i < clips.length; i++) { // 遍历每个片段
    const [start, end] = clips[i];         // 获取当前片段的开始和结束时间
    if (dp[start] == 101) { // 该片段上都覆盖不了,直接退出循环,保持为101
      break;
    }
    for (let j = start + 1; j <= end; j++) { // 计算当前片段上每个点的dp[j]
      dp[j] = Math.min(dp[j], dp[start] + 1);
    }
  }

  if (dp[T] == 101) {
    return -1;
  }
  return dp[T];
};
US-B.Ralph
LeetCode数据结构与算法算法

11 Comments

  • 头像
    recep ivedik izle

    I got what you mean,saved to bookmarks, very nice web site. Charmian Hershel Alysa

  • 头像
    erotik film izle

    Wow, this paragraph is fastidious, my younger sister is analyzing these kinds of things, therefore I am going to let know her. Bill Cordy Delanty

  • 头像
    sikis izle

    There is certainly a lot to know about this issue. I love all the points you made. Allina Ralph Charline

  • 头像
    erotik

    I am truly happy to glance at this web site posts which includes plenty of helpful information, thanks for providing these kinds of information. Lucila Dan Sherilyn

  • 头像
    erotik izle

    Muchos Gracias for your blog post. Much thanks again. Great. Marybeth Pieter Marceau

  • 头像
    film

    I am actually happy to read this website posts which consists of plenty of valuable information, thanks for providing such information. Penni Billie Swithbert

  • 头像
    film

    There is certainly a great deal to know about this topic. I love all of the points you made. Kirbie Warren Seftton

  • 头像
    film

    My name is Kobie Odling. And I am a professional academic writer with many years of experience in writing. Milena Brock Baun

  • 头像
    erotik

    Thanks again for the blog post. Really thank you! Much obliged. Cele Skell Faunia

  • 头像
    erotik izle

    I really liked your article post. Thanks Again. Really Great. Junette Rem Grous

  • 头像
    erotik izle

    What a material of un-ambiguity and preserveness of valuable knowledge about unexpected emotions. Gratia Horatius Nissie

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注