算法通关村第十七关-白银挑战贪心算法高频题目
大家好我是苏麟 , 今天说说贪心算法的高频题目 .
大纲
- 区间问题
- 判断区间是否重叠
- 合并区间
- 插入区间
区间问题
判断区间是否重叠
描述 :
给定一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间intervalsl[i] = [start, end] ,请你判断一个人是否能够参加这里面的全部会议。
题目 ;
LeetCode 252.会议室
这题需要开会员 , 有实力的小伙伴做一下 .
分析 :
因为一个人在同一时刻只能参加一个会议,因此题目实质是判断是否存在重叠区间,将区间按照会议开始时间进行排序,然后遍历一遍判断后面的会议开始的时候是否前面的还没有结束即可。也就是上图中如果出现重叠的部分就直接返回false即可
解析 :
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b) -> a[0] - b[0]);for(int i = 1; i < intervals.length;i++){if(intervals[i][0] < intervals[i - 1][1]){return false;}}return true;}
}
合并区间
描述 :
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
题目 :
LeetCode 56. 合并区间 :
合并区间
分析 :
为了方便理解,我们将上述序列画成序列图
和上一题一样,首先对区间按照起始端点进行升序排序,然后逐个判断当前区间是否与前一个区间重叠如果不重叠的话将当前区间直接加入结果集,反之如果重叠的话,就将当前区间与前一个区间进行合并 .
这里给一个非常好的视频解析 : 合并区间
解析 :
class Solution {public int[][] merge(int[][] intervals) {if(intervals == null || intervals.length == 0){return new int[][]{};}Arrays.sort(intervals,(a,b) -> a[0] - b[0]);List<int[]> list = new ArrayList<>();int start = intervals[0][0];int end = intervals[0][1];for(int[] arr : intervals){if(arr[0] <= end){end = Math.max(end , arr[1]);}else{list.add(new int[]{start,end});start = arr[0];end = arr[1];}}list.add(new int[]{start,end});return list.toArray(new int[][]{});}
}
插入区间
描述 :
给你一个 无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
题目 :
LeetCode 57. 插入区间:
插入区间
分析 :
本题就是上一题的再拓展,本题中的区间已经按照起始端点升序排列,因此我们直接遍历区间列表,寻找新区间的插入位置即可。具体步骤如下:
- 首先将新区间左边且相离的区间加入结果集 (遍历时,如果当前区间的结束位置小于新区间的开始位15置,说明当前区间在新区间的左边且相离)
- 接着判断当前区间是否与新区间重叠,重叠的话就进行合并,直到遍历到当前区间在新区间的右边且相离,将最终合并后的新区间加入结果集
- 最后将新区间右边且相离的区间加入结果集
这里也给一个非常好的解析视频 : 插入区间
解析 :
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {if(intervals == null){return new int[][]{};}List<int[]> list = new ArrayList<>();int i = 0;while(i < intervals.length && newInterval[0] > intervals[i][1]){list.add(intervals[i++]);}while(i < intervals.length && newInterval[1] >= intervals[i][0]){newInterval[0] = Math.min(intervals[i][0],newInterval[0]);newInterval[1] = Math.max(intervals[i++][1],newInterval[1]);}list.add(newInterval);while(i < intervals.length){list.add(intervals[i++]);}return list.toArray(new int[][]{});}
}
这期就到这里 , 下期见啊!
相关文章:

算法通关村第十七关-白银挑战贪心算法高频题目
大家好我是苏麟 , 今天说说贪心算法的高频题目 . 大纲 区间问题判断区间是否重叠合并区间插入区间 区间问题 判断区间是否重叠 描述 : 给定一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间intervalsl[i] [start, end] ,请你…...
【数据结构】动态规划(Dynamic Programming)
一.动态规划(DP)的定义: 求解决策过程(decision process)最优化的数学方法。 将多阶段决策过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。 二.动态规划的基本思想: …...

Redis key过期删除机制实现分析
文章目录 前言Redis key过期淘汰机制惰性删除机制定时扫描删除机制 前言 当我们创建Redis key时,可以通过expire命令指定key的过期时间(TTL),当超过指定的TTL时间后,key将会失效。 那么当key失效后,Redis会立刻将其删除么&#…...
ElasticSearch 谈谈分词与倒排索引的原理
ElasticSearch是一个基于Lucene的搜索服务器。Lucene是Java的一个全文检索工具包,而ElasticSearch则是一个分布式搜索和分析引擎。下面,我们将详细讨论ElasticSearch中的分词和倒排索引的原理。 分词: 在ElasticSearch中,分词是…...
【Java】Java8重要特性——Lambda函数式编程以及Stream流对集合数据的操作
【Java】Java8重要特性——Lambda函数式编程以及Stream流对集合数据的操作 前言Lambda函数式编程Stream流对集合数据操作(一)创建Stream流(二)中间操作之filter(三)中间操作之map(四)…...

大话数据结构-查找-散列表查找(哈希表)
注:本文同步发布于稀土掘金。 8 散列表查找(哈希表) 8.1 定义 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。查找时,根据这个确定的对应关系找到给…...

持续集成交付CICD:Sonarqube自动更新项目质量配置
目录 一、实验 1.Sonarqube手动自定义质量规则并指定项目 2.Sonarqube自动更新项目质量配置 一、实验 1.Sonarqube手动自定义质量规则并指定项目 (1)自定义质量规则 ①新配置 ②更多激活规则③根据需求激活相应规则④已新增配置 ⑤ 查看 &#x…...
Linux设置Docker自动创建Nginx容器脚本
文章目录 前言一、本地新建脚本二、复制本地脚本到服务器三、执行服务器脚本总结如有启发,可点赞收藏哟~ 前言 一、本地新建脚本 在本地新建nginx-generator.sh脚本文件,并保存以下内容 主要动态定义两个变量(容器名称/服务器本地文件名、端…...

技术博客:Vue中各种混淆用法汇总
技术博客:Vue中各种混淆用法汇总 摘要 本文主要介绍了在Vue中使用的一些常见混淆用法,包括new Vue()、export default {}、createApp()、Vue.component、Vue3注册全局组件、Vue.use()等,以及如何使用混淆器对代码进行加固,保护应…...

【python】Python生成GIF动图,多张图片转动态图,pillow
pip install pillow 示例代码: from PIL import Image, ImageSequence# 图片文件名列表 image_files [car.png, detected_map.png, base64_image_out.png]# 打开图片 images [Image.open(filename) for filename in image_files]# 设置输出 GIF 文件名 output_g…...

python/matlab图像去雾/去雨综述
图像去雾和去雨是计算机视觉领域的两个重要任务,旨在提高图像质量和可视化效果。本文将综述图像去雾和去雨的算法、理论以及相关项目代码示例。 一、图像去雾算法 基于暗通道先验的方法: 这是广泛应用于图像去雾的经典算法之一。该方法基于一个观察&…...

Docker+jenkins+gitlab实现持续集成
1.安装环境 服务器ip虚拟机版本192.168.5.132centos7.6192.168.5.152centos7.6 2. 安装docker 安装必要的一些系统工具 yum install -y yum-utils device-mapper-persistent-data lvm2添加软件源信息,要确保centos7能上外网 yum-config-manager --add-repo http:…...

Web前端JS如何获取 Video/Audio 视音频声道(左右声道|多声道)、视音频轨道、音频流数据
写在前面: 根据Web项目开发需求,需要在H5页面中,通过点击视频列表页中的任意视频进入视频详情页,然后根据视频的链接地址,主要是 .mp4 文件格式,在进行播放时实时的显示该视频的音频轨道情况,并…...

MySQL生成UUID并去除-
uuid()函数 uuid() 函数可以使mysql生成uuid,但是uuid中存在-,如下图: 去除uuid的- 默认生成的uuid含有-,我们可以使用replace函数替换掉-,SQL如下 select replace(uuid(),"-","") as uuid;Insert语句中使用UUID 如果…...

包与字符串
包是分类管理的需要,建立包用:package,包中类的引用import 学习使用javaAPI中的字符串类String,学会其成员方法的使用 (必看)eclipse包的分层等级结构设置 因为eclipse的包的结构默认是平行等级的,所以要手…...

【Gradle】mac环境安装Gradle及配置
官网安装说明:Gradle | Installation 由于Gradle运行依赖jvm,所以事先需要安装jdk,并确认你的jdk版本和gradle版本要求的对应关系,这个官网上有说明,但是我试了一下不太准确,供参考,链接如下&a…...

使用C语言操作kafka ---- librdkafka
1 安装librdkafka git clone https://github.com/edenhill/librdkafka.git cd librdkafka git checkout v1.7.0 ./configure make sudo make install sudo ldconfig 在librdkafka的examples目录下会有示例程序。比如consumer的启动需要下列参数 ./consumer <broker> &…...

误用STM32串口发送标志位 “USART_FLAG_TXE” “USART_FLAG_TC”造成的BUG
当你使用串口发送数据时是否出现过这样的情况: 1.发送时第一个字节丢失。 2.发送时出现莫名的字节丢失。 3.各种情况字节丢失。 1.先了解一下串口发送的流程图(手动描绘): 可以假想USART_FLAG_TXE是用于检测"弹仓"&…...

指针(三)
函数指针 定义:整型指针是指向整形的指针,数组指针式指向数组的指针,其实函数指针就是指向函数的指针。 函数指针基础: ()优先级要高于*;一个变量除去了变量名,便是它的变量类型;一个指针变量…...
labelimg遇到的标签修改问题:修改一张图像的标签时,保存后导致classes.txt改变
问题描述:修改一张图像的标签时候, classes.txt 会同步更新,导致重新生成了 classes.txt 但是这个 classes.txt 只有你现在写的那个类别名,以前的没有了。 解决:设置一个 predefined_classes.txt,内容和模…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...

【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...