算法训练营 day39 贪心算法 无重叠区间 划分字母区间 合并区间
算法训练营 day39 贪心算法 无重叠区间 划分字母区间 合并区间
无重叠区间
435. 无重叠区间 - 力扣(LeetCode)
给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
右边界排序之后,局部最优:优先选右边界小的区间,所以从左向右遍历,留给下一个区间的空间大一些,从而尽量避免交叉。全局最优:选取最多的非交叉区间。
这里记录非交叉区间的个数还是有技巧的,如图:

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));int count = 1;int end = intervals[0][1];for (int i = 1; i <intervals.length; i++) {if (end<=intervals[i][0]){end = intervals[i][1];count++;}}return intervals.length-count;}
}
划分字母区间
763. 划分字母区间 - 力扣(LeetCode)
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。
可以分为如下两步:
- 统计每一个字符最后出现的位置
- 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
如图:

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> result = new ArrayList<>();int[] hash = new int[26];char[] ch = s.toCharArray();for (int i = 0; i < ch.length; i++) {hash[ch[i]-'a'] = i;}int left = 0;int right = 0;for (int i = 0; i < ch.length; i++) {right = Math.max(right,hash[ch[i]-'a']);if (right==i){result.add(right-left+1);left = i+1;}}return result;}
}
合并区间
56. 合并区间 - 力扣(LeetCode)
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
按照左边界排序,排序之后局部最优:每次合并都取最大的右边界,这样就可以合并更多的区间了,整体最优:合并所有重叠的区间。
照左边界排序,排序之后局部最优:每次合并都取最大的右边界,这样就可以合并更多的区间了,整体最优:合并所有重叠的区间。
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int start = intervals[0][0];int end = intervals[0][1];for (int i = 1; i <intervals.length; i++) {if (end<intervals[i][0]){res.add(new int[]{start,end});start = intervals[i][0];end = intervals[i][1];}else {end = Math.max(end,intervals[i][1]);}}res.add(new int[]{start, end});return res.toArray(new int[res.size()][]);}
}
相关文章:
算法训练营 day39 贪心算法 无重叠区间 划分字母区间 合并区间
算法训练营 day39 贪心算法 无重叠区间 划分字母区间 合并区间 无重叠区间 435. 无重叠区间 - 力扣(LeetCode) 给定一个区间的集合 intervals ,其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互…...
c/c++开发,无可避免的文件访问开发案例
一、缓存文件系统 ANSI C标准中的C语言库提供了fopen, fclose, fread, fwrite, fgetc, fgets, fputc, fputs, freopen, fseek, ftell, rewind等标准函数,这些函数在不同的操作系统中应该调用不同的内核API,从而支持开发者跨平台实现对文件的访问。 在Lin…...
MySQL学习笔记
MySQL学习笔记一、基础配置二、数据库操作三、表的操作1.创建表2.表选项3.查看表4.修改表5.删除表6.复制表7.检查优化修复表四、数据操作基础增删改查五、字符集编码六、数据类型(列类型)1.数值类型2.字符串类型3.日期时间类型4.枚举和集合七、列属性&am…...
ccs导入工程失败的处理方法
文章目录当导入CCS新工程时出现下述错误怎么办?方法一 从TI官网下载安装包进行安装,下载链接:软件下载完成 安装路径为上面的文件夹点击安装完成后,导入安装路径,并点击Refresh按钮,依据路径进行更新&#…...
探针台常见的故障及解决方法
症状、 可能原因、 解决方法 移动样品后画面变模糊 —显微镜不垂直,调垂直显微镜 样品台不水平 —调水平样品台 显微镜视场亮度不足,边缘切割或看不到像—转换器不在定位位置上 把转换器转到定位位置上 管镜转盘不在定位位置上 —把管镜转盘转到定…...
域内资源探测
✅作者简介:CSDN内容合伙人、信息安全专业在校大学生🏆 🔥系列专栏 :内网安全 📃新人博主 :欢迎点赞收藏关注,会回访! 💬舞台再大,你不上台,永远是…...
c# 将数据导出到EXCEL文件
第一步:项目中加入引用。 在鼠标右击项目,点击【添加】弹出菜单列表,选择【项目引用】弹出【引用管理器】对话框,选择【COM】-【Microsoft Excel 16.0 Object Library】,如图所示: 第二步,编辑…...
微服务 分片 运维管理
微服务 分片 运维管理分片分片的概念分片案例环境搭建案例改造成任务分片Dataflow类型调度代码示例运维管理事件追踪运维平台搭建步骤使用步骤分片 分片的概念 当只有一台机器的情况下,给定时任务分片四个,在机器A启动四个线程,分别处理四个…...
批量占满TEMP表空间问题处理与排查
批量占满TEMP表空间问题处理与排查应急处置问题排查查看占用TEMP表空间高的SQL获取目标SQL执行计划方法一:EXPLAIN PLAN FOR方法二:DBMS_XPLAN.DISPLAY_CURSOR方法三:DBMS_XPLAN.DISPLAY_AWR方法四:AUTOTRACE数据库跑批任务占满TE…...
Pytorch中的tensor和variable
Tensor与Variable pytorch两个基本对象:Tensor(张量)和Variable(变量) 其中,tensor不能反向传播,variable可以反向传播(forword)。 反向传播是为了让神经网络更新前面…...
暗月内网渗透实战——项目七
首先环境配置 VMware的网络配置图 环境拓扑图 开始渗透 信息收集 使用kali扫描一下靶机的IP地址 靶机IP:192.168.0.114 攻击机IP:192.168.0.109 获取到了ip地址之后,我们扫描一下靶机开放的端口 靶机开放了21,80,999,3389,5985,6588端口…...
【Java 面试合集】描述下Objec类中常用的方法(未完待续中...)
描述下Objec类中常用的方法 1. 概述 首先我们要知道Object 类是所有的对象的基类,也就是所有的方法都是可以被重写的。 那么到底哪些方法是我们常用的方法呢??? cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringw…...
SQLSERVER 的 truncate 和 delete 有区别吗?
一:背景 1. 讲故事 在面试中我相信有很多朋友会被问到 truncate 和 delete 有什么区别 ,这是一个很有意思的话题,本篇我就试着来回答一下,如果下次大家遇到这类问题,我的答案应该可以帮你成功度过吧。 二࿱…...
【C++】CC++内存管理
就是你被爱情困住了?Wake up bro! 文章目录一、C/C内存分布二、C语言中动态内存管理方式三、C中内存管理方式1.new和delete操作内置类型2.new和delete操作自定义类型(仅限vs的底层实现机制,new和delete一定要匹配使用,…...
数据预处理之图像去空白
数据预处理之图像去空白图像去空白介绍方法边缘检测阈值处理形态学图像剪切图像去空白 介绍 图像去空白是指在图像处理中去除图像中的空白区域的过程。空白区域通常是指图像中的白色或其他颜色,其不包含有用的信息。去空白的目的是为了节省存储空间、提高图像处理…...
真的麻了,别再为难软件测试员了......
前言 有不少技术友在测试群里讨论,近期的面试越来越难了,要背的八股文越来越多了,考察得越来越细,越来越底层,明摆着就是想让我们徒手造航母嘛!实在是太为难我们这些测试工程师了。 这不,为了帮大家节约时…...
2月9日,30秒知全网,精选7个热点
///货拉拉将推出同城门到门跑腿服务 据介绍,两轮电动车将成为该业务的主要运力,预计将于3月中旬全面开放骑手注册和用户人气征集活动,并根据人气和线上骑手注册情况选择落地城市,于4月正式开放服务和骑手接单 ///三菱、乐天和莱茵…...
球面坐标系下的三重积分
涉及知识点 三重积分球面坐标系点火公式一些常见积分处理手法 球面坐标系定义 球面坐标系由方位角φ\varphiφ、仰角θ\thetaθ和距离rrr构成 直角坐标系(x,y,z)(x,y,z)(x,y,z)到球面坐标系的(r,φ,θ)(r,\varphi,\theta)(r,φ,θ)的转化规则如下: {xrsinφco…...
谷歌 Jason Wei | AI 研究的 4 项基本技能
文章目录 一、前言二、主要内容三、总结CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 原文作者为 Jason Wei,2020 年达特茅斯学院本科毕业,之后加入 Google Brain 工作。 Jason Wei 的博客主页:https://www.jasonwei.net/ 其实我不算是一个特别有经验的研究员…...
excel数据整理:合并计算快速查看人员变动
相信大家平时在整理数据时,都会对比数据是否有重复的地方,或者该数据与源数据相比是否有增加或者减少。数据量不大还好,数据量大的话,对比就比较费劲了。接下来我们将进入数据对比系列课程的学习。该系列一共有两篇教程࿰…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
