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

代码随想录第36、37天| 435. 无重叠区间 763.划分字母区间 56. 合并区间

 435. 无重叠区间

435. 无重叠区间 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

贪心算法,依然是判断重叠区间 | LeetCode:435.无重叠区间_哔哩哔哩_bilibili

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

提示:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

 没看卡哥题解,自己的想法就是先把区间从小到大排序,具体就是比较区间的最左边的值,也就是区间的最小值,最小值小的排前面。然后遍历每个区间,将第i个区间的left和第i-1区间的right值比较大小,left<=right则没有重叠,反之则有重叠,count++:

class Solution { // 定义一个类Solutionpublic int eraseOverlapIntervals(int[][] intervals) { // 定义一个公有方法eraseOverlapIntervals,接受一个二维整数数组intervals作为参数,并返回一个整数值Arrays.sort(intervals, (a,b)-> { // 使用Arrays.sort对intervals进行排序,排序规则是按照子数组的第一个元素升序排列return Integer.compare(a[0],b[0]); // 比较两个子数组的第一个元素的大小,返回比较结果});int remove = 0; // 初始化变量remove为0,用于记录需要移除的重叠区间数量int pre = intervals[0][1]; // 初始化变量pre为第一个区间的结束位置,用于记录上一个不重叠的区间的结束位置for(int i = 1; i < intervals.length; i++) { // 循环遍历intervals数组,从第二个区间开始if(pre > intervals[i][0]) { // 如果上一个区间的结束位置大于当前区间的开始位置,表示存在重叠remove++; // 计数器remove加1,表示需要移除一个重叠区间pre = Math.min(pre, intervals[i][1]); // 更新上一个不重叠区间的结束位置为当前区间的结束位置和上一个区间结束位置的较小值}else pre = intervals[i][1]; // 如果当前区间不与上一个区间重叠,则更新上一个不重叠区间的结束位置为当前区间的结束位置}return remove; // 返回需要移除的重叠区间数量}
}

763.划分字母区间 

763. 划分字母区间 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

贪心算法,寻找最远的出现位置! LeetCode:763.划分字母区间_哔哩哔哩_bilibili

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1:

输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。 

示例 2:

输入:s = "eccbbbbdec"
输出:[10]提示:
  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

这个题第一想法就是双指针法,一个指针i指向区间开头的字母,另外一个指针j从区间最左边向右遍历,直到找到和第一个字母相同的字母,返回这个字母的下标,然后指针i向右移动一位,指针j从原地右移;如果没找到,就把左边的指针i向后移动一位,重复上述过程。指针i和指针j的位置就是需要切割的位置。

写完发现好乱。。。。还是看卡哥题解吧。。

🤓看了卡哥题解后发现我有2点没弄清楚所以导致很乱:

1、区间与区间之间一定是不重合的,所以下一个区间起始的位置一定在上一个区间结束位置的后面

2、我最大的问题在于用双指针法很糊。不建议用双指针法,直接标出每个字母的下标,某字母下标最大的位置就是这个字母最远的位置,必须包括在同一个区间内,如图:

卡哥还有一点很巧妙的就是将字母转换成数字做减法,整体代码如下:

class Solution {public List<Integer> partitionLabels(String S) {// 创建一个列表来存储分区的长度List<Integer> list = new LinkedList<>();// 初始化一个数组来存储每个字符在字母表中的最后出现位置的索引int[] edge = new int[26];// 将输入字符串转换为字符数组char[] chars = S.toCharArray();// 遍历字符串的字符,存储每个字符的最后出现位置的索引for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i;}// 初始化变量来跟踪当前索引和当前分区的最后一个索引int idx = 0;int last = -1;// 再次遍历字符串的字符for (int i = 0; i < chars.length; i++) {// 更新当前分区的最后一个索引idx = Math.max(idx, edge[chars[i] - 'a']);// 如果当前索引等于当前分区的最后一个索引,// 这意味着我们已经到达当前分区的末尾if (i == idx) {// 将当前分区的长度添加到列表中list.add(i - last);// 更新当前分区的最后一个索引last = i;}}// 返回包含分区长度的列表return list;}
}

 56. 合并区间

56. 合并区间 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

贪心算法,合并区间有细节!LeetCode:56.合并区间_哔哩哔哩_bilibili

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

先按左边界的值排序:

发现重合后其实只需要更新右边界:

// 更新最右边界为当前区间右边界和原最右边界的较大值rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);

综合代码:

class Solution {public int[][] merge(int[][] intervals) {// 创建一个列表来存储合并后的区间List<int[]> res = new LinkedList<>();// 按照区间的左边界进行排序Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));// 初始化 start 为第一个区间的左边界int start = intervals[0][0];// 初始化最右边界为第一个区间的右边界int rightmostRightBound = intervals[0][1];// 遍历区间数组for (int i = 1; i < intervals.length; i++) {// 如果当前区间的左边界大于当前最右边界if (intervals[i][0] > rightmostRightBound) {// 将当前区间合并到结果中,并更新 start 和最右边界res.add(new int[]{start, rightmostRightBound});start = intervals[i][0];rightmostRightBound = intervals[i][1];} else {// 更新最右边界为当前区间右边界和原最右边界的较大值rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);}}// 添加最后一个合并后的区间到结果中res.add(new int[]{start, rightmostRightBound});// 将结果列表转换为数组并返回return res.toArray(new int[res.size()][]);}
}

 

 738.单调递增的数字

738. 单调递增的数字 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

贪心算法,思路不难想,但代码不好写!LeetCode:738.单调自增的数字_哔哩哔哩_bilibili

注意点:

1、这个题要注意从后往前遍历。

2、传进来的数值是int类型,为了方便各个位上的数值比较大小,将int类型转为字符串。

3、start记录位置,start后面的都赋值为9才能得到最大值

4、start初始为s的长度而不是0,为的就是避免s=1234这种情况出现时,再走for (int i = start; i < s.length(); i++) {
            chars[i] = '9'; 的逻辑将s变成1999.

class Solution {public int monotoneIncreasingDigits(int n) {// 将输入的整数转换为字符串String s = String.valueOf(n);// 将字符串转换为字符数组char[] chars = s.toCharArray();// 初始化变量 start 为字符串的长度int start = s.length();// 从倒数第二位开始向前遍历字符数组for (int i = s.length() - 2; i >= 0; i--) {// 如果当前字符大于后面一位字符if (chars[i] > chars[i + 1]) {// 将当前字符减去1,并更新 start 的值为当前位置的后一位chars[i]--;start = i + 1;}}// 将 start 位置后的所有字符设为 '9'for (int i = start; i < s.length(); i++) {chars[i] = '9';}// 将字符数组转换为整数并返回return Integer.parseInt(String.valueOf(chars));}
}

相关文章:

代码随想录第36、37天| 435. 无重叠区间 763.划分字母区间 56. 合并区间

435. 无重叠区间 435. 无重叠区间 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.com) 贪心算法&#xff0c;依然是判断重叠区间 | LeetCode&#xff1a;435.无重叠区间_哔哩哔哩_bilibili 给定一个区间的集合 intervals &#xff0c;其中 intervals[…...

代码学习记录40---动态规划

随想录日记part40 t i m e &#xff1a; time&#xff1a; time&#xff1a; 2024.04.10 主要内容&#xff1a;今天开始要学习动态规划的相关知识了&#xff0c;今天的内容主要涉及&#xff1a; 买卖股票的最佳时机加强版。 123.买卖股票的最佳时机III 188.买卖股票的最佳时机…...

java八股——消息队列MQ

上一篇传送门&#xff1a;点我 目前只学习了RabbitMQ&#xff0c;后续学习了其他MQ后会继续补充。 MQ有了解过吗&#xff1f;说说什么是MQ&#xff1f; MQ是Message Queue的缩写&#xff0c;也就是消息队列的意思。它是一种应用程序对应用程序的通信方法&#xff0c;使得应用…...

【前端Vue】Vue3+Pinia小兔鲜电商项目第5篇:整体认识和路由配置,本资源由 收集整理【附代码文档】

Vue3ElementPlusPinia开发小兔鲜电商项目完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;认识Vue3&#xff0c;使用create-vue搭建Vue3项目1. Vue3组合式API体验,2. Vue3更多的优势,1. 认识create-vue,2. 使用create-vue创建项目,1. setup选项的写法和执行…...

前端项目部署教程——有域名无证书

一、拉取nginx镜像 docker pull nginx //先拉取nginx镜像二、打包前端项目 1、将Vue打包项目传输到/usr/local/vue/下blog和admin文件夹下 2、在/usr/local/nginx下创建nginx.conf文件&#xff0c;格式如下&#xff1a; events {worker_connections 1024; }http {include …...

后端项目部署教程

一、打包jar包 lyamanoblog-server-0.0.1.jar ps:运行时可能会提醒不能有大写字母&#xff0c;所以用的都是小写字母 二、编写Dockerfile文件 FROM java:8 VOLUME /tmp ADD lyamanoblog-server-0.0.1.jarblog.jar ENTRYPOINT ["java","-Djava.securit…...

【微命令】git 如何修改某个分支的名字(git branch -m newbranch)

简要信息&#xff0c;快速记录 命令 # 切换到某个需要修改的分支 git checkout oldbranch# 修改分支名字 git branch -m newbranch假设作为git设计者&#xff0c;要用来修改branch的命令&#xff0c;那么就是 git branch作为前缀&#xff0c;然后进一步修改的命令是branch相关…...

Unity UI 优化技巧

将画布分割为多个 问题:当 UI Canvas 的任何元素发生变化时,都会影响整个 Canvas。 Canvas 是 Unity UI 的重要组成部分。它创建一个网格来表示放置在其顶部的 UI 元素,在 UI 元素更改时重建网格,并调用 GPU 来渲染实际的用户界面。 创建这些网络可能非常昂贵。UI 元素应…...

前端学习之DOM编程案例:抽奖案例

代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>抽奖案例</title><style>*{margin: 0;padding: 0;}</style> </head> <body><div id"container"&g…...

解决windows下Qt Creator显示界面过大的问题

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 问题描述 解决方法 1、右击此电脑--->属性 2、点击高级系统设置--->点击环境变量 3、 找到系…...

MySQL 通信协议 tcp c/s架构 jdbc java

简介 服务器启动后&#xff0c;会使用 TCP 监听一个本地端口&#xff0c;当客户端的连接请求到达时&#xff0c;就会执行三段握手以及 MySQL 的权限验证&#xff1b;验证成功后&#xff0c;客户端开始发送请求&#xff0c;服务器会以响应的报文格式返回数据&#xff1b;当客户…...

蓝桥杯第十三届电子类单片机组决赛程序设计

前言 一、决赛题目 1.比赛题目 2.题目解读 二、功能实现 1.关于定时器资源 1&#xff09;超声波和NE555需要的定时器资源 2&#xff09;定时器2 2.单位切换 3.数据长度不足时&#xff0c;高位熄灭 4.AD/DA多通道的处理 5.PWM输出 6.长按功能的实现 三、完整代码演…...

【Entity Framework】如何使用EF中的生成值

【Entity Framework】如何使用EF中的生成值 文章目录 【Entity Framework】如何使用EF中的生成值一、概述二、默认值三、计算列四、设置主键五、显示配置值生成六、设置日期/时间值生成6.1 创建时间戳6.2 更新时间戳 七、替代值生成八、无值生成九、总结 一、概述 数据库列的值…...

【MATLAB源码-第185期】基于matlab的16QAM系统相位偏移估计EOS算法仿真,对比补偿前后的星座图误码率。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 1. 引言 M-QAM调制技术的重要性 现代通信系统追求的是更高的数据传输速率和更有效的频谱利用率。M-QAM调制技术&#xff0c;作为一种高效的调制方案&#xff0c;能够通过在相同的带宽条件下传输更多的数据位来满足这一需求…...

C++入门语法(命名空间缺省函数函数重载引用内联函数nullptr)

目录 前言 1. 什么是C 2. C关键字 3. 命名空间 3.1 命名空间的定义 3.2 命名空间的使用 4. C输入和输出 5. 缺省函数 5.1 概念 5.2 缺省参数分类 6. 函数重载 6.1 概念 6.2 为何C支持函数重载 7. 引用 7.1 概念 7.2 特性 7.3 常引用 7.4 引用与指针的区别 7…...

9.vector的使用介绍和模拟实现

1.vector的介绍及使用 1.1 vector的介绍 vector的文档介绍 vector是表示可变大小数组的序列容器。 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c…...

探索设计模式的魅力:MVVM模式在AI大模型领域的创新应用-打破传统,迎接智能未来

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 MVVM模式在AI大模型领域的创新应用-打破传统迎接智能未来 &#x1f680; “在人工智能的领域里&a…...

Docker使用— Docker部署安装Nginx

Nginx简介 Nginx 是一款高性能的 web 服务器、反向代理服务器以及电子邮件&#xff08;IMAP/POP3/SMTP&#xff09;代理服务器&#xff0c;由俄罗斯开发者伊戈尔塞索耶夫&#xff08;Igor Sysoev&#xff09;编写&#xff0c;并在2004年10月4日发布了首个公开版本0.1.0。Nginx…...

C/C++基础----运算符

算数运算符 运算符 描述 例子 两个数字相加 两个变量a b得到两个变量之和 - 两个数字相减 - * 两个数字相乘 - / 两个数字相除 - % 两个数字相除后取余数 8 % 3 2 -- 一个数字递减 变量a&#xff1a;a-- 、--a 一个数字递增 变量a: a 、 a 其中递…...

YOLOv9:下一代目标检测的革新

目标检测作为计算机视觉领域的一个重要分支&#xff0c;一直是研究的热点。YOLO系列作为目标检测算法的佼佼者&#xff0c;自YOLO1发布以来&#xff0c;就在速度和精度上取得了很好的平衡&#xff0c;深受业界和学术界的喜爱。 YOLOv9作为该系列的最新版本&#xff0c;不仅在性…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...