算法通关村第十七关-白银挑战贪心算法高频题目
大家好我是苏麟 , 今天说说贪心算法的高频题目 .
大纲
- 区间问题
- 判断区间是否重叠
- 合并区间
- 插入区间
区间问题
判断区间是否重叠
描述 :
给定一个会议时间安排的数组 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:…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...