代码随想录算法训练营第三十五天|452. 用最少数量的箭引爆气球 435. 无重叠区间 763.划分字母区间

ops/2024/10/15 22:15:47/

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

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

  • 输入：points = [[10,16],[2,8],[1,6],[7,12]]
  • 输出：2
  • 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

  • 输入：points = [[1,2],[3,4],[5,6],[7,8]]
  • 输出：4

示例 3：

  • 输入：points = [[1,2],[2,3],[3,4],[4,5]]
  • 输出：2

示例 4：

  • 输入：points = [[1,2]]
  • 输出：1

示例 5：

  • 输入：points = [[2,3],[2,3]]
  • 输出：1

提示：

  • 0 <= points.length <= 10^4
  • points[i].length == 2
  • -2^31 <= xstart < xend <= 2^31 - 1

思路：

需要判断的条件并非是前后两个气球是否重叠来决定是否射箭，而是判断后一个气球是否与前一个气球的射箭点重叠。

而这个射箭点，初始默认为第一个气球和第二个气球的重叠部分的最右端（只要有重叠，重叠部分最左端一定是下一个气球的左端），但此时箭未射出，锁定瞄准点，同时忽略后一个气球超出重叠的部分（因为这部分不影响结果），所以将后一个气球的有边界更新为重叠部分最右端；若没有重叠部分，则是前一个气球的最右端，并且此时射出，计数加一。

以上为我根据解析得到的复述思路，以下附上规范解析：

如何使用最少的弓箭呢？

直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个气球，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？

尝试一下举反例，发现没有这种情况。

那么就试一试贪心吧！局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

算法确定下来了，那么如何模拟气球射爆的过程呢？是在数组中移除元素还是做标记呢？

如果真实的模拟射气球的过程，应该射一个，气球数组就remove一个元素，这样最直观，毕竟气球被射了。

但仔细思考一下就发现：如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。

以上为思考过程，已经确定下来使用贪心了，那么开始解题。

为了让气球尽可能的重叠，需要对数组进行排序。

那么按照气球起始位置排序，还是按照气球终止位置排序呢？

其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。

既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

从前向后遍历遇到重叠的气球了怎么办？

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。

规范代码：

class Solution:

    def findMinArrowShots(self, points: List[List[int]]) -> int:

        if len(points) == 0: return 0

        points.sort(key=lambda x: x[0])

        result = 1

        for i in range(1, len(points)):

            if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=

                result += 1     

            else:

                points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界

        return result

class Solution: # 不改变原数组

    def findMinArrowShots(self, points: List[List[int]]) -> int:

        points.sort(key = lambda x: x[0])

        sl,sr = points[0][0],points[0][1]

        count = 1

        for i in points:

            if i[0]>sr:

                count+=1

                sl,sr = i[0],i[1]

            else:

                sl = max(sl,i[0])

                sr = min(sr,i[1])

        return count

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

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

示例 2:

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

示例 3:

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

思路：第一感觉是和上一题射箭十分相似，但没想到还是没做出来，虽然照着上面代码一改就能AC，但是总觉得不是自己做出来的。

核心思路是找出非重叠区间个数，然后用总数减去非重叠区间个数就可以得到答案。通过右边界来进行排序，那么如果【后一个区间的左边界】小于【前一个区间的右边界】就一定是重合了，那么如何考虑【再下一个区间】呢，就是取 【前一个区间】 和 【后一个区间】 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。

按照左边界排序的话，可以直接求重叠的区间。

取边界的时候可以理解为，将超出重叠部分以右的部分是应该被移除的部分！

规范代码：

贪心 基于左边界

class Solution:

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:

        if not intervals:

            return 0

        

        intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序

        count = 0  # 记录重叠区间数量

        

        for 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])  # 更新重叠区间的右边界

                count += 1

        

        return count

贪心 基于左边界 把452.用最少数量的箭引爆气球代码稍做修改

class Solution:

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:

        if not intervals:

            return 0

        

        intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序

        

        result = 1  # 不重叠区间数量，初始化为1，因为至少有一个不重叠的区间

        

        for i in range(1, len(intervals)):

            if intervals[i][0] >= intervals[i - 1][1]:  # 没有重叠

                result += 1

            else:  # 重叠情况

                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  # 更新重叠区间的右边界

        

        return len(intervals) - result

763.划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

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

提示：

  • S的长度在[1, 500]之间。
  • S只包含小写字母 'a' 到 'z' 。

思路：

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

可以分为如下两步：

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

如图：

763.划分字母区间

规范代码：

class Solution:

    def partitionLabels(self, s: str) -> List[int]:

        last_occurrence = {}  # 存储每个字符最后出现的位置

        for i, ch in enumerate(s):

            last_occurrence[ch] = i

        result = []

        start = 0

        end = 0

        for i, ch in enumerate(s):

            end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置

            if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间

                result.append(end - start + 1)

                start = i + 1

        return result

贪心（版本二）与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。

class Solution:

    def countLabels(self, s):

        # 初始化一个长度为26的区间列表，初始值为负无穷

        hash = [[float('-inf'), float('-inf')] for _ in range(26)]

        hash_filter = []

        for i in range(len(s)):

            if hash[ord(s[i]) - ord('a')][0] == float('-inf'):

                hash[ord(s[i]) - ord('a')][0] = i

            hash[ord(s[i]) - ord('a')][1] = i

        for i in range(len(hash)):

            if hash[i][0] != float('-inf'):

                hash_filter.append(hash[i])

        return hash_filter

    def partitionLabels(self, s):

        res = []

        hash = self.countLabels(s)

        hash.sort(key=lambda x: x[0])  # 按左边界从小到大排序

        rightBoard = hash[0][1]  # 记录最大右边界

        leftBoard = 0

        for i in range(1, len(hash)):

            if hash[i][0] > rightBoard:  # 出现分割点

                res.append(rightBoard - leftBoard + 1)

                leftBoard = hash[i][0]

            rightBoard = max(rightBoard, hash[i][1])

        res.append(rightBoard - leftBoard + 1)  # 最右端

        return res


http://www.ppmy.cn/ops/126137.html

相关文章

Java 包装器一口气讲完！(≧∇≦)ﾉ

Java 包装器一口气讲完！(≧∇≦)ﾉ

目录 Java 数据类型包装器 Java数据类型教程 - Java数据类型包装器 方法 例子 valueOf() Java 数字数据类型 Java数据类型教程 - Java数字数据类型 例子 方法 值 Java 字符数据类型 Java数据类型教程 - Java字符数据类型 例子 Java Boolean包装类 Java数据类型教程…
阅读更多...
windows C++-避免死锁(下)

windows C++-避免死锁(下)

使用 join 防止死锁 下面介绍了如何使用消息缓冲区和消息传递函数来消除死锁的可能性。 为了将该示例与上一示例相关联&#xff0c;philosopher 类通过使用 concurrency::unbounded_buffer 对象和 join 对象来替换每个 critical_section 对象。 join 对象充当为哲学家提供筷子…
阅读更多...
mac下docker的详细安装和配置

mac下docker的详细安装和配置

linux的docker安装请参考&#xff1a;linux下docker详细安装&#xff0c;在Mac上安装Docker也相对简单&#xff0c;以下是详细步骤&#xff1a; 1. 系统要求 确保你的Mac满足以下要求&#xff1a; macOS 10.14&#xff08;Mojave&#xff09;或更高版本至少4GB RAM 2. 下载…
阅读更多...
img标签的title和alt的区别，png、jpg、gif、格式区别

img标签的title和alt的区别，png、jpg、gif、格式区别

img标签的title和alt有什么区别&#xff1f; 区别一&#xff1a; title&#xff1a;鼠标移入到图片显示的值 alt&#xff1a;图片无法加载时显示的值 区别二&#xff1a; 在seo的层面上&#xff0c;蜘蛛抓取不到图片的内容&#xff0c;所以前端在写img标签的时候为了增加seo效果…
阅读更多...
Java 多线程（三）—— 死锁

Java 多线程（三）—— 死锁

死锁的产生 我们先从简单的死锁最后到难一些的死锁问题开始展开讨论。 首先一个线程&#xff0c;一把锁&#xff0c;因为多次加锁而导致死锁问题&#xff0c;由于Java 的synchronized 实现了可重入锁&#xff0c;因此这个死锁问题就不存在了&#xff0c;意味着当一个线程拥有…
阅读更多...
测试用例的编写

测试用例的编写

1.基本概念&#xff1a; 编写测试用例是确保代码质量和正确性的重要环节&#xff0c;尤其是在软件开发和维护过程中。测试用例通常用于验证功能是否符合预期&#xff0c;并及时发现潜在的错误或漏洞。 2.常见的测试用例编写方法&#xff1a; 等价划分法&#xff0c;边界值法&a…
阅读更多...
线性回归损失函数的推导

线性回归损失函数的推导

要推导损失函数公式 ℓ ( θ ) 1 2 n ( y ^ − y ) ⊤ ( y ^ − y ) \ell(\boldsymbol{\theta}) \frac{1}{2n}(\hat{\boldsymbol{y}} - \boldsymbol{y})^\top(\hat{\boldsymbol{y}} - \boldsymbol{y}) ℓ(θ)2n1​(y^​−y)⊤(y^​−y)&#xff0c;我们可以从几个基础概念开…
阅读更多...
安装R和RStudio：开始你的数据分析之旅

安装R和RStudio：开始你的数据分析之旅

数据分析是当今世界中一个非常热门的领域&#xff0c;而R语言是进行数据分析的强大工具之一。R是一种编程语言和软件环境&#xff0c;用于统计计算和图形表示。RStudio是一个集成开发环境&#xff08;IDE&#xff09;&#xff0c;它为R语言提供了一个更加友好和高效的工作环境。…
阅读更多...
最新文章

Copyright @ 2022~2023