个人练习-Leetcode-1024. Video Stitching

这篇具有很好参考价值的文章主要介绍了个人练习-Leetcode-1024. Video Stitching。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:https://leetcode.cn/problems/video-stitching/

题目大意:给出一个视频长度time,再给出一串clips[][]每个clip中clip[0]代表起始时间,clip[1]代表结束时间。求能够覆盖[0, time]的所需的最小clip数。

思路:贪心算法。用farest[i]代表以i位置为起始时间能够到达的最远的结束时间(抱歉这里用“远”来形容时间,实际上把这个什么时间看成一个条带、一个区间都是一样的)。这样保证了如果该clip如果被选上,那它一定是所有相同起点内最优的那个clip。随后循环即可:

0开始,用last记录当前能到达的最远的时间。那么从上一次结束的遍历位置pos开始,在last之前,寻找能到达的最远的时间。为什么要在last之前呢?因为如果poslast之后了,找的clip就是从last+1开始,那其实是之后的循环要做的事情,现在不必要。相当于我们一次找到一个最优的clip,这个clip和上一个clip必定是衔接的。

然而如果一开始pos就比last大,说明中间必定有片段缺失了,我们无法凑成完整的[0, time],直接返回-1

int last = farest[0], ret = 1, pos = 0;
        while (last < time && pos < time) {
            if (pos > last) return -1;
            int des = farest[pos], d_pos = pos;
            pos++;
            while (pos <= last) {
                if (farest[pos] > des) {
                    des = farest[pos];
                    d_pos = pos;
                }
                pos++;
            }
            if (des > last) {
                last = des;
                ret++;
                if (last >= time) break;
            }
        }  

注意:题目有点坑的地方是,给出的区间可能有超过给定时间time的clip,因此最后的返回判断应该是大于等于号

完整代码文章来源地址https://www.toymoban.com/news/detail-400420.html

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> farest(101, -1);
        for (auto clip : clips) {
            farest[clip[0]] = max(farest[clip[0]], clip[1]);
        }

        int last = farest[0], ret = 1, pos = 0;
        while (last < time && pos < time) {
            if (pos > last) return -1;
            int des = farest[pos], d_pos = pos;
            pos++;
            while (pos <= last) {
                if (farest[pos] > des) {
                    des = farest[pos];
                    d_pos = pos;
                }
                pos++;
            }
            if (des > last) {
                last = des;
                ret++;
                if (last >= time) break;
            }
        }  

        if (last >= time)
            return ret;
        else 
            return -1;
    }
};

到了这里,关于个人练习-Leetcode-1024. Video Stitching的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【递增栈】个人练习-Leetcode-845. Longest Mountain in Array

    题目链接:https://leetcode.cn/problems/longest-mountain-in-array/ 题目大意:给出一个数组 arr[] ,定义【山数组】为【长度大于等于3】【前面部分递增,后面部分递减,存在一个山峰元素】的数组。求 arr[] 中的最长的是【山数组】的子列。 思路:递增栈当然可以,不过刚好想到另一个

    2024年02月06日
    浏览(51)
  • 【贪心】个人练习-Leetcode-2195. Append K Integers With Minimal Sum

    题目链接:https://leetcode.cn/problems/append-k-integers-with-minimal-sum/ 题目大意:给出一个数组 nums[] ,现在要往里面追加 k 个【互不相同】且【未出现在 nums[] 中】的【正整数】,使得这 k 个数字之和最小。 思路:明显就是贪心,从 1 开始塞进去即可。但是单纯的【累加+用set判断是

    2024年02月02日
    浏览(48)
  • 【DFS+剪枝】个人练习-Leetcode-面试题 16.04. Tic-Tac-Toe LCCI

    题目链接:https://leetcode.cn/problems/tic-tac-toe-lcci/ 题目大意:给出一个 N*N 的棋盘格 board[][] ,走圈叉棋,判断输赢情况,某一方赢了返回该方的字符,若平局(棋盘满且没有一方赢)返回 Draw ,若结局未定(棋盘未满且没有一方赢)返回 Pending 思路:可以DFS做,并做一部分剪枝

    2024年02月02日
    浏览(36)
  • Leetcode.1024 视频拼接

    Leetcode.1024 视频拼接 rating : 1746 你将会获得一系列视频片段,这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。 使用数组 clips 描述所有的视频片段,其中 c l i p s [ i ] = [ s t a r t i , e n d i ] clips[i] = [start_i, end_i] c l i p s [ i ] = [ s t

    2024年02月11日
    浏览(30)
  • 【Microsoft Azure 的1024种玩法】六十.通过Azure Virtual Machines快速搭建个人Ghost博客系统

    Ghost 是一套基于Node.js 语言开发构建的开源博客系统,它的整体架构为前端管理系统基于Ember.js, 后端的模板引擎采用的handlebars, 数据库是基于MySQL的,本篇文章主要介绍了如何通过Azure Virtual Machines快速搭建个人Ghost博客系统 【Microsoft Azure 的1024种玩法】一.一分钟快速上手搭

    2024年02月06日
    浏览(39)
  • PYTHON-模拟练习题目集合

     🌈write in front🌈 🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如需转载还请通知⚠️ 📝个人主页:Aileen_0v0🧸—CSDN博客 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​ 📣系列专栏:Aileen_0

    2024年02月07日
    浏览(36)
  • 记录--Js基础练习题目

    提示:  document.write可以在页面中打印内容 br 在 html 中代表换行 ,   在 html 中代码空格   提示:使用循环 第一层 for 循环控制方格 , 第二层 for 循环控制方格里面放的芝麻数量   提示:输入值为数组,执行方法后要返回数组里面的所有数值的和 提示:使用switch 分情况处理

    2024年02月07日
    浏览(60)
  • JavaScript题目练习1

    1.for循环打印九九乘法表 2.打印倒三角形,十行十列 3.运用while/ do-while循环计算1~100之间所有整数的和  4.求数组中最大值    [2,4,63,54,34,6,67,35,16]  5.将数组[\\\'red\\\',\\\'green\\\',\\\'pink\\\',\\\'blue\\\']转换为字符串,并用|分割 结果:red|green|pink|blue| 6.数组反转[\\\'red\\\',\\\'green\\\',\\\'pink\\\',\\\'blue\\\',\\\'purple\\\'] 结果:

    2023年04月09日
    浏览(29)
  • Go的并发练习题目

    现在有4个协程,分别对应编号为1,2,3,4,每秒钟就有一个协程打印自己的编号,要求编写一个程序,让输出的编号总是按照1,2,3,4,1,2,3,4这样的规律一直打印下去 使用chan来实现程序的graceful shutdown,在程序退出之前来执行一些连接的关闭,文件的close相关操作。

    2024年01月20日
    浏览(59)
  • 动态规划题目练习

    动态规划背包问题-CSDN博客 动态规划基础概念-CSDN博客 题目描述 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河

    2024年04月25日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包