代码随想录算法训练营第36天(py)| 贪心 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间

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

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

力扣链接
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。
给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。

思路

当气球出现重叠,一起射,所用弓箭最少。为了让气球尽可能的重叠,需要对数组进行排序。把气球排序之后,从前到后遍历气球,被射过的气球跳过即可。
在这里插入图片描述
如果气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points)==0:return 0points.sort(key = lambda x:x[0])#按照左边界排序res = 1for i in range(len(points)):if points[i][0] > points[i-1][1]: # 如果不重合res += 1else: # 如果重合points[i][1] = min(points[i - 1][1], points[i][1]); # 更新重叠气球最小右边界return res

435. 无重叠区间

力扣链接
给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。(区间可以“接触”,但不能“重叠”)

思路

按照左边界排序,统计重叠区间数量即可

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if len(intervals)==0:return 0intervals.sort(key = lambda x:x[0])#按照左边界排序cnt = 0for i in range(1,len(intervals)):if intervals[i][0] < intervals[i-1][1]: #存在重叠intervals[i][1] = min(intervals[i-1][1], intervals[i][1]) #更新重叠区间cnt += 1return cnt 

763.划分字母区间

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

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

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

思路

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

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

在这里插入图片描述


class Solution:def partitionLabels(self, s: str) -> List[int]:last_appear = {} #哈希表记录字符最后出现的位置for index, char in enumerate(s):last_appear[char] = indexres = []start = 0end = 0for index, char in enumerate(s):end = max(last_appear[char], end)if index == end:#res.append(s[start:end+1])res.append(end - start + 1)start = end + 1return res

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



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

相关文章

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#调

一文教你Python引入其他文件夹下的.py文件

《一文教你Python引入其他文件夹下的.py文件》这篇文章主要为大家详细介绍了如何在Python中引入其他文件夹里的.py文件,并探讨几种常见的实现方式,有需要的小伙伴可以根据需求进行选择... 目录1. 使用sys.path动态添加路径2. 使用相对导入(适用于包结构)3. 使用pythonPATH环境

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

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

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js