【代码随想录算法训练营Day35】435.无重叠区间;763.划分字母区间;56.合并区间

news/2024/4/16 14:43:02/文章来源:https://blog.csdn.net/Tammy2001/article/details/136464783

文章目录

  • ❇️Day 36 第八章 贪心算法 part05
    • ✴️今日任务
    • ❇️435. 无重叠区间
      • 自己的思路
      • 自己的代码(✅通过81.59%)
      • 随想录思路
      • 随想录代码
    • ❇️763.划分字母区间
      • 自己的思路
      • 自己的代码(✅通过55.30%)
      • 随想录思路
      • 随想录代码
    • ❇️56. 合并区间
      • 自己的思路
      • 自己的代码(82.47%)
      • 随想录思路
      • 随想录代码

❇️Day 36 第八章 贪心算法 part05

✴️今日任务

今天的三道题目,都算是 重叠区间 问题,大家可以好好感受一下。 都属于那种看起来好复杂,但一看贪心解法,惊呼:这么巧妙!
还是属于那种,做过了也就会了,没做过就很难想出来。
不过大家把如下三题做了之后, 重叠区间 基本上差不多了

  • 435.无重叠区间
  • 763.划分字母区间
  • 56.合并区间

❇️435. 无重叠区间

  • 题目链接:https://leetcode.cn/problems/non-overlapping-intervals/
  • 视频讲解:https://www.bilibili.com/video/BV1A14y1c7E1
  • 文章链接:https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html

自己的思路

还和452一样,通过先确定右区间再判断左区间的方式
区别:当重叠时count++

自己的代码(✅通过81.59%)

class Solution {public int eraseOverlapIntervals(int[][] intervals) {int count = 0;Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] points1, int[] points2) {if (points1[1] > points2[1]) {return 1;} else if (points1[1] < points2[1]) {return -1;}return 0;}});//for(int[] i :intervals) System.out.println(Arrays.toString(i));int end = 0; //被取右区间的范围下标int start = 1; //被取左区间的下标while(start < intervals.length){//System.out.println("次数:"+count);//重叠if(intervals[start][0] < intervals[end][1]){count ++;//System.out.println("气球{"+intervals[start][0]+", "+intervals[start][1]+"}可同时和气球{"+intervals[end][0]+", "+intervals[end][1]+"}一起被扎破");}else{end = start;}start ++;}return count;}
}

随想录思路

我来按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的,如图:
在这里插入图片描述

随想录代码

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[0],b[0]);});int count = 1;for(int i = 1;i < intervals.length;i++){if(intervals[i][0] < intervals[i-1][1]){intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);continue;}else{count++;}}return intervals.length - count;}
}

❇️763.划分字母区间

  • 题目链接:https://leetcode.cn/problems/partition-labels/
  • 视频讲解:https://www.bilibili.com/video/BV18G4y1K7d5
  • 文章链接:https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html

自己的思路

  1. 定义一个二维数组的数组int count[26][]来存储字母最开始出现的下标和最后出现的下标
  2. 遍历字符串得到每个字母出现的区间
  3. 定义最小左区间和最大右区间

自己的代码(✅通过55.30%)

class Solution {public List<Integer> partitionLabels(String s) {int count[][] = new int[26][2];List<Integer> res = new ArrayList<>();for (int i = 1; i < s.length(); i++) {if(count[s.charAt(i)-'a'][1] == 0){if(s.charAt(i) != s.charAt(0)) {count[s.charAt(i) - 'a'][0] = i;}count[s.charAt(i)-'a'][1] = i;}else{count[s.charAt(i)-'a'][1] = i;}}Arrays.sort(count, (a,b)-> {return Integer.compare(a[0],b[0]);});int left = 0;int right = count[0][1];for (int i = 0; i < 26; i++) {if(count[i][1] != 0) {if(count[i][0] <= right){right = Math.max(right, count[i][1]);}else{res.add(right - left + 1);left = count[i][0];right = count[i][1];}}}res.add(right - left + 1);return res;}
}

随想录思路

在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。
可以分为如下两步:

  • 统计每一个字符最后出现的位置
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

如图:
[图片]

随想录代码

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. 合并区间

  • 本题相对来说就比较难了
  • 题目链接:https://leetcode.cn/problems/merge-intervals/
  • 视频讲解:https://www.bilibili.com/video/BV1wx4y157nD
  • 文章链接:https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

自己的思路

  1. 先对二维数组进行排序
  2. 判断后一个的左区间是否在前一个的右区间内
  3. 定义一个栈用来存放备选结果

自己的代码(82.47%)

public static int[][] merge(int[][] intervals) {//当二维数组只有一个一维数组时返回该一维数组if(intervals.length == 1) return intervals;//定义一个结果二维数组LinkedList<int[]> res = new LinkedList<>();//count是结果二维数组的长度,当有重叠长度-1int count = intervals.length;//排序二维数组Arrays.sort(intervals,(a,b) -> a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]);//定义当前右区间int right = intervals[0][1];//将第一个数组加入备选区间res.push(intervals[0]);//从第二个区间开始遍历for (int i = 1; i < intervals.length; i++) {//如果这个和上一个区间有重叠if(intervals[i][0] <= right){//长度--count --;//更新右区间right = Math.max(intervals[i][1], right);//更新备选区间的右区间if(res.peek() != null && res.peek()[1] != right) {res.peek()[1] = right;}}else{//当没有重叠的时候直接加入备选区间res.push(intervals[i]);//更新用来对比的右区间right = intervals[i][1];}}return res.toArray(new int[count][]);
}

随想录思路

和我的基本一样

随想录代码

优化点:

  1. 栈的res.peek()可以换成res.removeLast();
  2. 可以去掉count,直接换成res.size()
public int[][] merge(int[][] intervals) {LinkedList<int[]> res = new LinkedList<>();Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= res.getLast()[1]) {int start = res.getLast()[0];int end = Math.max(intervals[i][1], res.getLast()[1]);res.removeLast();res.add(new int[]{start, end});}else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997754.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

0101二阶与三阶行列式-行列式-线性代数

一 引例 求解二元一次方程组 { a 11 x 1 a 12 x 2 b 1 a 21 x 1 a 22 x 2 b 2 \begin{cases} a_{11}x_1a_{12}x_2b_1\\ a_{21}x_1a_{22}x_2b_2\\ \end{cases} {a11​x1​a12​x2​b1​a21​x1​a22​x2​b2​​ 解&#xff1a; 1 a 21 − 2 a 11 ⇒ x 2 a 11 b 2 − a…

IPSec VPN配置实验

什么是IPSec VPN&#xff1f; IPSec VPN其实就是一种基于互联网协议安全&#xff08;IPSec&#xff09;的虚拟私人网络技术&#xff0c;它通过在IP层加密和认证数据包来确保数据传输的安全性。 IPSec VPN的主要特点包括&#xff1a; 安全性&#xff1a;IPSec提供了强大的安全…

游戏视频怎么录制?超实用的干货来了!

随着游戏产业的蓬勃发展&#xff0c;游戏视频录制与分享已经成为许多玩家和游戏爱好者展示技巧、分享经验、记录精彩瞬间的重要方式。可是很多人不知道游戏视频怎么录制&#xff0c;本文旨在为广大游戏玩家提供两种简单易用的游戏视频录制方法&#xff0c;这两种方法各有特点&a…

校园小情书微信小程序,社区小程序前后端开源,校园表白墙交友小程序

功能 表白墙卖舍友步数旅行步数排行榜情侣脸漫画脸个人主页私信站内消息今日话题评论点赞收藏 效果图

代码随想录刷题笔记-Day31

1. 分发饼干 455. 分发饼干https://leetcode.cn/problems/assign-cookies/ 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口…

如何在Linux用Docker部署MySQL数据库并远程访问本地数据库

文章目录 前言1 .安装Docker2. 使用Docker拉取MySQL镜像3. 创建并启动MySQL容器4. 本地连接测试4.1 安装MySQL图形化界面工具4.2 使用MySQL Workbench连接测试 5. 公网远程访问本地MySQL5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定TCP地址远程访问 前言 本文主…

事务失效的八种情况!!!!

EnableAspectJAutoProxy(exposeProxy true)&#xff0c;开启AOP&#xff08;面向切面编程&#xff09;代理&#xff0c;并允许通过AopContext类暴露当前代理对象。这样&#xff0c;你可以在任何地方获取到当前代理对象&#xff0c;以便进行一些特殊的操作 &#xff08;应用与第…

Visual Studio如何进行类文件的管理(类文件的分离)

大家好&#xff1a; 衷心希望各位点赞。 您的问题请留在评论区&#xff0c;我会及时回答。 一、问题背景 实际开发中&#xff0c;类的声明放在头文件中&#xff0c;给程序员看类的成员和方法。比如&#xff1a;Dog.h&#xff08;类的声明文件&#xff09; 类的成员函数的具体…

【Linux】深入探究CentOS防火墙(Firewalld):基础概念、常用命令及实例操作

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Linux ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 Firewalld基础概念&#xff1a; Firewalld常用命令&#xff1a; 启动/停止/重启Firewalld服务&#xff1a; 查看Firewalld状态…

#QT(智能家居界面-布局)

1.IDE&#xff1a;QTCreator 2.实验&#xff1a; 水平布局&#xff0c;垂直布局&#xff0c;栅格布局&#xff08;弹簧&#xff09; 界面自动调整 3.记录 注意弹簧不是拖拽拉长&#xff0c;而是使用栅格布局 运行发现窗口放大缩小可以自动调整 如果想要重新布局&#xff0c;需…

【Git】深入理解 Git 分支合并操作:git merge dev 命令详解

深入理解 Git 合并操作&#xff1a;git merge dev 命令详解 摘要&#xff1a;本文将深入探讨 Git 中的合并操作&#xff0c;以及如何使用 git merge dev 命令将dev 分支的修改合并到当前分支&#xff08;假设当前分支为main 分支&#xff09;中。通过详细的解释和示意图&#x…

文献速递:深度学习疾病预后--临床级计算病理学使用基于整张切片图像的弱监督深度学习

Title 题目 Clinical-grade computational pathology using weakly supervised deep learning on whole slide images 临床级计算病理学使用基于整张切片图像的弱监督深度学习 01 文献速递介绍 The development of decision support systems for pathology and their deplo…

java SSM科研管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM科研管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S…

C# 由左上、右下两个坐标点计算矩形的长、宽以及两点的距离

一、计算长、宽 直接使用坐标点计算 // 定义矩形左上角和右下角的坐标 Point topLeft new Point(0, 0); Point bottomRight new Point(5, 10); // 计算矩形的长和宽 int width bottomRight.X - topLeft.X;//矩形宽度 int height bottomRight.Y - topLeft.Y;//矩形高度或是…

谷粒商城实战(002 oss 文件储存系统)

Java项目《谷粒商城》架构师级Java项目实战&#xff0c;对标阿里P6-P7&#xff0c;全网最强 总时长 104:45:00 共408P 此文章包含第61p-第p101的内容 简介 P61 服务器 对象存储服务 OSS 也可以用minio 三种上传方式 推荐第三种 1.过服务器 安全 但是占用性能 2.不过服…

natfrp和FRP配置SSL的基本步骤和bug排查

获取免费/付费SSL 我直接买了一年的ssl证书 设置 主要参考&#xff1a;https://doc.natfrp.com/frpc/ssl.html 遇到的Bug root域名解析是ALIAS&#xff0c;不是CNAME不要用NATFRP &#xff08;SakuraFrp&#xff09;同步Joplin&#xff0c;会出现webdav错误导致大量笔记被…

哈希专题 - leetcode 1. 两数之和 - 简单难度

leetcode 1. 两数之和 leetcode 1. 两数之和 简单难度 哈希1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理3. 时间复杂度 3. 代码实现4. 知识与收获 leetcode 1. 两数之和 简单难度 哈希 1. 题目详情 给定一个整数数组 nums 和一个整数目标值 target…

go语言基础 -- 单元测试

go语言testing框架说明 go语言有自己的测试框架,封装在testing包中。 我们编写的测试案例通常都写在xxx_test.go文件中,比如我们写了个calc.go,对里面的函数进行测试,通常会写一个calc_test.go;testing框架会将_test.go结尾的文件引入;testing框架会在自己的main方法中执…

2024.3.4 JAVA 复习

Java环境搭建 1、JDK和JRE的概述 JDK&#xff1a;Java开发工具包(Java Development Kit), 包含开发工具 和 JRE. 常用的开发工具: javac, java JRE&#xff1a;Java运行时环境(Java Runtime Environment), 包含运行Java程序时所需的核心类库和 JVM. 核心类库: java.lang, jav…

Node.js作用

Node.js可以开发应用 开发服务器应用 开发工具类应用 开发桌面端应用