【代码随想录】【算法训练营】【第36天】[452]用最少数量的箭引爆气球 [435]无重叠区间 [763]划分字母区间

本文主要是介绍【代码随想录】【算法训练营】【第36天】[452]用最少数量的箭引爆气球 [435]无重叠区间 [763]划分字母区间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

思路及算法思维,指路 代码随想录。
题目来自 LeetCode。

day 36,周三,最难坚持的一天~

题目详情

[452] 用最少数量的箭引爆气球

题目描述

452 用最少数量的箭引爆气球
452 用最少数量的箭引爆气球

解题思路

前提:区间可能重叠
思路:贪心算法:按照起始位置排序,一支箭尽可能射多的气球。
重点:判断当前弓箭终止范围。

代码实现

C语言
贪心思维

局部最优:当气球出现重叠,一起射,所用弓箭最少。
全局最优:把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠,需要对数组进行排序。
如果气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

int cmp(const void *p1, const void *p2)
{int *pp1 = *(int **)p1;int *pp2 = *(int **)p2;// 按照起始位置排序, 相同起始位置按终止位置排序if (pp1[0] > pp2[0]) {return 1;}else if (pp1[0] == pp2[0]) {if (pp1[1] > pp2[1]) {return 1;}}return 0;
}int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){// 按照起始位置排序, 相同起始位置按终止位置排序qsort(points, pointsSize, sizeof(int *), cmp);// 至少需要一支箭int count = 1;int curRange = points[0][1];for (int i = 1; i < pointsSize; i++) {// 判断是否需要使用下一只弓箭:当前射箭范围是否与当前数组范围有交集if (curRange < points[i][0]) {count++;curRange = points[i][1];}// 判断当前数组范围是否会缩小当前射箭范围if (curRange > points[i][1]) {curRange = points[i][1];}}return count;
}

[435] 无重叠区间

题目描述

435 无重叠区间
435 无重叠区间

解题思路

前提:区间可能重叠
思路:贪心算法:按照起始位置排序,判断区间是否重复,去除重复区间时去除更大的区间,留下较小的区间。
重点:判断当前区间终止范围。

代码实现

C语言
起始位置排序,判断重复区间

按照起始位置排序,起始位置相同按照终止位置排序,判断区间是否重复,去除重复区间时去除更大的区间,留下较小的区间

int cmp(const void *p1, const void *p2)
{int *pp1 = *(int **)p1;int *pp2 = *(int **)p2;return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp1[0] - pp2[0];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {// 按照起始位置排序,起始位置相同按照终止位置排序qsort(intervals, intervalsSize, sizeof(int *), cmp);int count = 0;int endNum = intervals[0][1];// 判断区间是否重复,去除重复区间时去除更大的区间,留下较小的区间for (int i = 1; i < intervalsSize; i++) {// 判断起始位置与之前终止位置是否重叠if (endNum > intervals[i][0]) {count++;}else {endNum = intervals[i][1];}// 更新终止位置if (endNum > intervals[i][1]) {endNum = intervals[i][1];}}return count;
}
终止位置排序,判断非交叉区间

按照终止位置排序,终止位置相同按照起始位置排序,判断非重复区间的个数,需要移除区间数量即为重复区间个数,即总区间个数 - 非重复区间个数

int cmp(const void *p1, const void *p2)
{int *pp1 = *(int **)p1;int *pp2 = *(int **)p2;return pp1[1] == pp2[1] ? pp1[0] - pp2[0] : pp1[1] - pp2[1];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {// 按照终止位置排序,终止位置相同按照起始位置排序qsort(intervals, intervalsSize, sizeof(int *), cmp);int count = 1;int endNum = intervals[0][1];// 判断非重复区间的个数for (int i = 1; i < intervalsSize; i++) {// 判断起始位置与之前终止位置是否重叠if (endNum <= intervals[i][0]) {count++;endNum = intervals[i][1];}}// 需要移除区间数量即为重复区间个数,即总区间个数 - 非重复区间个数return intervalsSize - count;
}

[763] 划分字母区间

题目描述

763 划分字母区间
763 划分字母区间

解题思路

前提:同一字母处于同一子字符串中
思路:要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点。
重点:确定分割点的位置,经过的每个字符串的最远位置。

代码实现

C语言
贪心思维

统计每个字母最后出现的位置;圈字符,找分割点;遍历到当前元素出现的最远位置,即为分割点。

/*** Note: The returned array must be malloced, assume caller calls free().*/#define LETTERS_MAX_NUMS  (26)int* partitionLabels(char* s, int* returnSize) {int sLen = strlen(s);int range[LETTERS_MAX_NUMS];// 统计每个字母最后出现的位置for (int i = 0; i < sLen; i++) {range[s[i] - 'a'] = i;   }// 输出初始化int *ans = (int *)malloc(sizeof(int) * LETTERS_MAX_NUMS);int ansSize = 0;// 划分尽可能多的片段, 每个片段尽可能短,但是要包含所有同一字母// 圈字符,找分割点int left = 0;int right = 0;for (int i = 0; i < sLen; i++) {// 缓存当前元素的最远位置if (right < range[s[i] - 'a']) {right = range[s[i] - 'a'];}// 遍历到当前元素出现的最远位置,即为分割点if (i == right) {ans[ansSize] = i - left + 1;ansSize++;left = i + 1;}}*returnSize = ansSize;return ans;
}

今日收获

  1. 贪心算法:不太能想到的思路。

这篇关于【代码随想录】【算法训练营】【第36天】[452]用最少数量的箭引爆气球 [435]无重叠区间 [763]划分字母区间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1058308

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时