当前位置: 首页 > news >正文

算法训练营 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. 无重叠区间 - 力扣&#xff08;LeetCode&#xff09; 给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互…...

c/c++开发,无可避免的文件访问开发案例

一、缓存文件系统 ANSI C标准中的C语言库提供了fopen, fclose, fread, fwrite, fgetc, fgets, fputc, fputs, freopen, fseek, ftell, rewind等标准函数&#xff0c;这些函数在不同的操作系统中应该调用不同的内核API&#xff0c;从而支持开发者跨平台实现对文件的访问。 在Lin…...

MySQL学习笔记

MySQL学习笔记一、基础配置二、数据库操作三、表的操作1.创建表2.表选项3.查看表4.修改表5.删除表6.复制表7.检查优化修复表四、数据操作基础增删改查五、字符集编码六、数据类型&#xff08;列类型&#xff09;1.数值类型2.字符串类型3.日期时间类型4.枚举和集合七、列属性&am…...

ccs导入工程失败的处理方法

文章目录当导入CCS新工程时出现下述错误怎么办&#xff1f;方法一 从TI官网下载安装包进行安装&#xff0c;下载链接&#xff1a;软件下载完成 安装路径为上面的文件夹点击安装完成后&#xff0c;导入安装路径&#xff0c;并点击Refresh按钮&#xff0c;依据路径进行更新&#…...

探针台常见的故障及解决方法

症状、 可能原因、 解决方法 移动样品后画面变模糊 —显微镜不垂直&#xff0c;调垂直显微镜 样品台不水平 —调水平样品台 显微镜视场亮度不足&#xff0c;边缘切割或看不到像—转换器不在定位位置上 把转换器转到定位位置上 管镜转盘不在定位位置上 —把管镜转盘转到定…...

域内资源探测

✅作者简介&#xff1a;CSDN内容合伙人、信息安全专业在校大学生&#x1f3c6; &#x1f525;系列专栏 &#xff1a;内网安全 &#x1f4c3;新人博主 &#xff1a;欢迎点赞收藏关注&#xff0c;会回访&#xff01; &#x1f4ac;舞台再大&#xff0c;你不上台&#xff0c;永远是…...

c# 将数据导出到EXCEL文件

第一步&#xff1a;项目中加入引用。 在鼠标右击项目&#xff0c;点击【添加】弹出菜单列表&#xff0c;选择【项目引用】弹出【引用管理器】对话框&#xff0c;选择【COM】-【Microsoft Excel 16.0 Object Library】&#xff0c;如图所示&#xff1a; 第二步&#xff0c;编辑…...

微服务 分片 运维管理

微服务 分片 运维管理分片分片的概念分片案例环境搭建案例改造成任务分片Dataflow类型调度代码示例运维管理事件追踪运维平台搭建步骤使用步骤分片 分片的概念 当只有一台机器的情况下&#xff0c;给定时任务分片四个&#xff0c;在机器A启动四个线程&#xff0c;分别处理四个…...

批量占满TEMP表空间问题处理与排查

批量占满TEMP表空间问题处理与排查应急处置问题排查查看占用TEMP表空间高的SQL获取目标SQL执行计划方法一&#xff1a;EXPLAIN PLAN FOR方法二&#xff1a;DBMS_XPLAN.DISPLAY_CURSOR方法三&#xff1a;DBMS_XPLAN.DISPLAY_AWR方法四&#xff1a;AUTOTRACE数据库跑批任务占满TE…...

Pytorch中的tensor和variable

Tensor与Variable pytorch两个基本对象&#xff1a;Tensor&#xff08;张量&#xff09;和Variable&#xff08;变量&#xff09; 其中&#xff0c;tensor不能反向传播&#xff0c;variable可以反向传播&#xff08;forword&#xff09;。 反向传播是为了让神经网络更新前面…...

暗月内网渗透实战——项目七

首先环境配置 VMware的网络配置图 环境拓扑图 开始渗透 信息收集 使用kali扫描一下靶机的IP地址 靶机IP&#xff1a;192.168.0.114 攻击机IP&#xff1a;192.168.0.109 获取到了ip地址之后&#xff0c;我们扫描一下靶机开放的端口 靶机开放了21,80,999,3389,5985,6588端口…...

【Java 面试合集】描述下Objec类中常用的方法(未完待续中...)

描述下Objec类中常用的方法 1. 概述 首先我们要知道Object 类是所有的对象的基类&#xff0c;也就是所有的方法都是可以被重写的。 那么到底哪些方法是我们常用的方法呢&#xff1f;&#xff1f;&#xff1f; cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringw…...

SQLSERVER 的 truncate 和 delete 有区别吗?

一&#xff1a;背景 1. 讲故事 在面试中我相信有很多朋友会被问到 truncate 和 delete 有什么区别 &#xff0c;这是一个很有意思的话题&#xff0c;本篇我就试着来回答一下&#xff0c;如果下次大家遇到这类问题&#xff0c;我的答案应该可以帮你成功度过吧。 二&#xff1…...

【C++】CC++内存管理

就是你被爱情困住了&#xff1f;Wake up bro&#xff01; 文章目录一、C/C内存分布二、C语言中动态内存管理方式三、C中内存管理方式1.new和delete操作内置类型2.new和delete操作自定义类型&#xff08;仅限vs的底层实现机制&#xff0c;new和delete一定要匹配使用&#xff0c;…...

数据预处理之图像去空白

数据预处理之图像去空白图像去空白介绍方法边缘检测阈值处理形态学图像剪切图像去空白 介绍 图像去空白是指在图像处理中去除图像中的空白区域的过程。空白区域通常是指图像中的白色或其他颜色&#xff0c;其不包含有用的信息。去空白的目的是为了节省存储空间、提高图像处理…...

真的麻了,别再为难软件测试员了......

前言 有不少技术友在测试群里讨论&#xff0c;近期的面试越来越难了&#xff0c;要背的八股文越来越多了,考察得越来越细&#xff0c;越来越底层&#xff0c;明摆着就是想让我们徒手造航母嘛&#xff01;实在是太为难我们这些测试工程师了。 这不&#xff0c;为了帮大家节约时…...

2月9日,30秒知全网,精选7个热点

///货拉拉将推出同城门到门跑腿服务 据介绍&#xff0c;两轮电动车将成为该业务的主要运力&#xff0c;预计将于3月中旬全面开放骑手注册和用户人气征集活动&#xff0c;并根据人气和线上骑手注册情况选择落地城市&#xff0c;于4月正式开放服务和骑手接单 ///三菱、乐天和莱茵…...

球面坐标系下的三重积分

涉及知识点 三重积分球面坐标系点火公式一些常见积分处理手法 球面坐标系定义 球面坐标系由方位角φ\varphiφ、仰角θ\thetaθ和距离rrr构成 直角坐标系(x,y,z)(x,y,z)(x,y,z)到球面坐标系的(r,φ,θ)(r,\varphi,\theta)(r,φ,θ)的转化规则如下&#xff1a; {xrsin⁡φco…...

谷歌 Jason Wei | AI 研究的 4 项基本技能

文章目录 一、前言二、主要内容三、总结CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 原文作者为 Jason Wei,2020 年达特茅斯学院本科毕业,之后加入 Google Brain 工作。 Jason Wei 的博客主页:https://www.jasonwei.net/ 其实我不算是一个特别有经验的研究员…...

excel数据整理:合并计算快速查看人员变动

相信大家平时在整理数据时&#xff0c;都会对比数据是否有重复的地方&#xff0c;或者该数据与源数据相比是否有增加或者减少。数据量不大还好&#xff0c;数据量大的话&#xff0c;对比就比较费劲了。接下来我们将进入数据对比系列课程的学习。该系列一共有两篇教程&#xff0…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...