@ 代码随想录算法训练营第6周(C语言)|Day36(贪心)
@ 代码随想录算法训练营第6周(C语言)|Day36(贪心)
Day36、贪心(包含题目 ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间 )
435. 无重叠区间
题目描述
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
题目解答
int cmp(const void *p1,const void *p2){int *pp1=*(int**)p1;int*pp2=*(int**)p2;return pp1[0]-pp2[0];
}
int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {if(intervalsSize==0){return 0;}qsort(intervals,intervalsSize,sizeof(int*),cmp);int res=0;int end=intervals[0][1];for(int i=1;i<intervalsSize;i++){if(intervals[i][0]>=end){end=intervals[i][1];}else{end=end<intervals[i][1]?end:intervals[i][1];res++;}}return res;
}
题目总结
排序、重叠就加一并更新区间。
763.划分字母区间
题目描述
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
题目解答
int* partitionLabels(char* s, int* returnSize) {int *res=(int*)malloc(sizeof(int)*26);int ssize=strlen(s);int hash[26];for(int i=0;i<ssize;i++){hash[s[i]-'a']=i;}//每个字母最后出现的位置int right=0;int left=0;int count=0;for(int i=0;i<ssize;i++){right=right>hash[s[i]-'a']?right:hash[s[i]-'a'];if(right==i){res[count++]=right-left+1;left=right+1;}}*returnSize=count;return res;}
题目总结
用哈希表来记录字母最后出现位置,然后一旦遍历过的字母最大值与坐标值相同就是边界。
56. 合并区间
题目描述
给出一个区间的集合,请合并所有重叠的区间。
题目解答
int cmp(const void *p1,const void *p2){int *pp1=*(int**)p1;int *pp2=*(int**)p2;return pp1[0]-pp2[0];}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {int**res=(int**)malloc(sizeof(int*)*intervalsSize);int count=0;qsort(intervals,intervalsSize,sizeof(int*),cmp);res[count]=intervals[0];for(int i=1;i<intervalsSize;i++){if( res[count][1]>=intervals[i][0]){res[count][1]= res[count][1]>intervals[i][1]? res[count][1]:intervals[i][1];}else{res[++count]=intervals[i];}}count++;*returnSize=count;*returnColumnSizes=malloc(sizeof(int)*count);for(int i=0;i<count;i++){(*returnColumnSizes)[i]=2;}return res;
}
题目总结
根扎气球相同,更新已经记录的数组区间。
相关文章:
@ 代码随想录算法训练营第6周(C语言)|Day36(贪心)
代码随想录算法训练营第6周(C语言)|Day36(贪心) Day36、贪心(包含题目 ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间 ) 435. 无重叠区间 题目描述 给定一个区间的集合,找到需要…...
数组打印杨辉三角
签名:但行好事,莫问前程。 文章目录 前言一、杨辉三角的概念二、二维数组打印杨辉三角1、创建二维数组2、使用for循环,初始化外层元素3、给数组赋值3.1给数组每行首末元素赋值为13.1给数组每行非首末元素赋值 三、杨辉三角全代码总结 前言 记…...
【操作系统·考研】文件系统
1.概述 文件系统(File System)提供高效和便捷的磁盘访问,以便允许存储、定位、提取数据。 严格来说,VFS并不是一种实际的FS,它只存在于内存中,不存在与任何外存空间中。 VFS在系统启动时建立,在系统关闭时消亡。 2.结…...
中国传媒网CEO徐晓艺荣膺第九届金鸥奖“2023年度最佳创新人物”殊荣
2023年是不平凡的一年,风云变幻。大国经济有韧性,离不开顶层设计、宏观政策的指挥,也离不开千百万求新求变的企业和企业家们的辛勤耕耘。在经历了三年疫情严峻考验的当下,中国号巨轮迎风搏浪心如磐石,无惧险阻屹立潮头,这不仅是中国红的底色,也是中国企业家的坚守和倔强。2023年…...
ElementUI Form:Switch 开关
ElementUI安装与使用指南 Switch 开关 点击下载learnelementuispringboot项目源码 效果图 el-switch.vue (Switch 开关)页面效果图 项目里el-switch.vue代码 <script> export default {name: el_switch,data() {return {value: true,value1: …...
通俗易懂理解注意力机制(Attention Mechanism)
重要说明:本文从网上资料整理而来,仅记录博主学习相关知识点的过程,侵删。 一、参考资料 大话注意力机制(Attention Mechanism) 注意力机制(Attention Mechanism) 深度学习中的注意力机制 注意力机制 二、注意力…...
git的分支的使用,创建分支,合并分支,删除分支,合并冲突,分支管理策略,bug分支,强制删除分支
GIT | 分支 文章目录 GIT | 分支创建分支合并分支删除分支合并冲突分支管理策略bug分支强制删除分支 创建分支 查看当前本地仓库中有哪些分支 git branchHEAD所指向的分支就是当前正在工作的分支 cat .git/HEAD创建一个分支 git branch dev创建好了,但是目前还是…...
【leetcode100-081到090】【动态规划】一维五题合集1
【爬楼梯】 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 思路: 【状态】 dp[i];//爬i级台阶有几种方法 【初始】 dp[0] 1;//爬0级1种(不爬)dp[1] 1;/…...
数据结构-顺序表详解专题
目录 顺序表 1.简单了解顺序表 2.顺序表的分类 2.1静态顺序表 2.2动态顺序表 2.3typedef命名作用 3.动态顺序表的实现 SeqList.h SeqList.c test.c 顺序表 1.简单了解顺序表 顺序表是线性表的一种,线性表是在逻辑上是线性结构,在物理逻辑上并…...
对商业知识和思维的一些小体会
用途:个人学习笔录,欢迎指正 前言: 小生拙见,我认为商业知识和商业思维的理解对于每一个行业都有潜在的帮助,因为每个人的生活都离不开商业,生意、工作都是交换,用自身提供的价值换取薪酬。因此…...
【笔记】计算文件夹的大小
目标:遍历文件夹,计算文件夹下包含文件和文件夹的大小。将这些结果存入python自带的数据库。 用大模型帮我设计并实现。 Step1 创建一个测试用的目录结构 创建目录结构如下所示: TestDirectory/ │ ├── EmptyFolder/ │ ├── SmallF…...
机器学习_常见算法比较模型效果(LR、KNN、SVM、NB、DT、RF、XGB、LGB、CAT)
文章目录 KNNSVM朴素贝叶斯决策树随机森林 KNN “近朱者赤,近墨者黑”可以说是 KNN 的工作原理。 整个计算过程分为三步: 计算待分类物体与其他物体之间的距离;统计距离最近的 K 个邻居;对于 K 个最近的邻居,它们属于…...
外包干了8个月,技术退步明显...
先说一下自己的情况,大专生,18年通过校招进入武汉某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...
opencv#41 轮廓检测
轮廓概念介绍 通常我们使用二值化的图像进行轮廓检测,对轮廓以外到内进行数字命名,如下图,最外面的轮廓命名为0,向内部进行扩展,遇到黑色白色相交区域,就是一个新的轮廓,然后依次对轮廓进行编号…...
Websocket基本用法
1.Websocket介绍 WebSocket是基于TCP的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手,两者之间就可以创建持久性的连接,并进行双向数据传输。 应用场景: 视频弹幕网页聊天体育实况更新股票基金…...
node.js与express.js创建项目以及连接数据库
搭建项目 一、技术准备 node版本:16.16.0 二、安装node成功后,安装express,命令如下: npm install -g express 或者: npm install --locationglobal express 再安装express的命令工具: npm install --location…...
【Tomcat与网络8】从源码看Tomcat的层次结构
在前面我们介绍了如何通过源码来启动Tomcat,本文我们就来看一下Tomcat是如何一步步启动的,以及在启动过程中,不同的组件是如何加载的。 一般,我们可以通过 Tomcat 的 /bin 目录下的脚本 startup.sh 来启动 Tomcat,如果…...
Java Agent Premain Agentmain
概念 premain是在jvm启动的时候类加载到虚拟机之前执行的 agentmain是可以在jvm启动后类已经加载到jvm中了,才去转换类。 这种方式会转换会有一些限制,比如不能增加或移除字段。 具体的做法,两者的实际做法是差不多的: premain 定义个静…...
Python实现设计模式-策略模式
策略模式是一种行为型设计模式,它定义了一系列算法或策略,并将它们封装成独立的类,使得它们可以相互替换,而不影响客户端的使用。 在策略模式中,算法或策略被封装在单独的策略类中,这些策略类实现了相同的…...
详解SpringCloud微服务技术栈:深入ElasticSearch(4)——ES集群
👨🎓作者简介:一位大四、研0学生,正在努力准备大四暑假的实习 🌌上期文章:详解SpringCloud微服务技术栈:深入ElasticSearch(3)——数据同步(酒店管理项目&a…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
