IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 贪心算法(二) | 重叠区间问题 | leecode刷题笔记 -> 正文阅读

[数据结构与算法]贪心算法(二) | 重叠区间问题 | leecode刷题笔记

跟随carl代码随想录刷题
语言:python


55. 跳跃游戏

题目:给定一个非负整数数组 nums ,你最初位于数组的 第一个下标
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
👉示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
👉示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

题目分析

转化为覆盖问题
在这里插入图片描述

完整代码如下

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        if len(nums) == 1:
            return True
        
        i = 0
        while i <= cover:  # 用于控制前面覆盖的范围包括当前i索引的
            cover = max(i+nums[i], cover)
            if cover >= len(nums) - 1:  # 判断覆盖范围是否涵盖了整个数组
                return True
            i += 1
        return False

45. 跳跃游戏 II

题目:给你一个非负整数数组 nums ,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
👉示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
👉示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

题目分析

以最小的步数增加最大的覆盖范围,直到覆盖范围覆盖了终点。
待分析……

完整代码如下

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        
        ans = 0
        curDistance = 0
        nextDistance = 0
        for i in range(len(nums)):
            nextDistance = max(i + nums[i], nextDistance)
            if i == curDistance: 
                if curDistance != len(nums) - 1:
                    ans += 1
                    curDistance = nextDistance
                    if nextDistance >= len(nums) - 1: break
        return ans

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

题目:有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。
给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。
👉示例 1:
输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8]和[1,6]。
-在x = 11处发射箭,击破气球[10,16]和[7,12]。
👉示例 2:
输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。
👉示例 3:
输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:

  • 在x = 2处发射箭,击破气球[1,2]和[2,3]。
  • 在x = 4处射出箭,击破气球[3,4]和[4,5]。

题目分析

  • python知识介绍:对二维数组进行排序二维数组.sort()
    • 执行key = lambda函数
    • x: x[0]表示对二维数组中的每个元组的第一维排序
    • x: x[1]表示对二维数组中的每个元组的第二维排序
    • eg:对points = [[10,16], [2,8], [1,6], [7,12]]排序
      • points.sort(key = lambda x: x[0])
        • [[1,6], [2,8], [7,12]], [10,16]] # 对左边界排序
      • points.sort(key = lambda x: x[1])
        • [[1,6], [2,8], [7,12], [10,16]] # 对右边界排序

解题思路:
请添加图片描述
气球被引爆的条件:

  • 题目中说xstart <= x <= xend可以被引爆
  • 因此引爆情况有两种:
    • 区间重合,eg:[1, 3], [2, 5]
    • 区间相邻,eg:[1, 2], [2, 3]
    • 代码
      • point[i][0] <= point[i-1][1] # 后一个气球的左边界start 小于等于 前一个气球的右边界end
      • 更新 后一个气球的右边界endpoint[i][1] = point[i-1][1]

在这里插入图片描述

完整代码如下

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
    	# 如果没有气球,返回0
        if len(points) == 0: return 0

		# 对气球的区间进行排序
        points.sort(key=lambda x: x[0])
        
        count = 1  # 记录非交叉区间的个数,区间数初始化为1
        
        for i in range(1, len(points)):
            if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着,注意这里不是>=
                count += 1  # 区间数+1     
            else:
                points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界
        return count

435. 困难无重叠区间

题目:给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
👉示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
👉示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
👉示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

题目分析

  • 目标:求需要移除的交叉区间的数量
  • 可以转化为:求return——总区间数 - 非交叉区间的数量

本题和452.用最少数量的箭引爆气球非常像,弓箭的数量交叉区间数量+相邻区间数量。而本题中在判断条件加个等号变成>=(认为只要区间2的左端点 大于等于 区间1的右端点,就是不重合的区间数。然后用总区间数减去不重合的区间数就是要移除的区间数量了。

完整代码如下

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0: 
        	return 0
        
        # 排序	
        intervals.sort(key=lambda x: x[0])
        
        count = 1  # 记录非交叉区间的个数,初始化为1
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= intervals[i - 1][1]: # 区间i和区间i-1挨着。intervals[i - 1][1]是区间分割点
                count += 1     
            else:
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]) # 更新重叠气球最小右边界
        return len(intervals) - count

763. 划分字母区间

题目:字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
👉示例:
输入:S = “ababcbacadefegdehijhklij”
输出:[9,7,8]
解释:
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的,因为划分的片段数较少。

题目分析

本题是分割字符串,不过不用回溯。

如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。

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

将区间按左边界从小到大排序,找到边界将区间划分成组,互不重叠。找到的边界就是答案。

完整代码如下

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hash = [0]*26  # 26个英文字母
        for i in range(len(s)):
            hash[ord(s[i]) - ord('a')] = i  # ASCII码
        result = []
        left = 0
        right = 0
        for i in range(len(s)):
            right = max(right, hash[ord(s[i]) - ord('a')])
            if i == right:
                result.append(right - left + 1)
                left = i + 1
        return result

56. 合并区间

题目:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
👉示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
👉示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

题目分析

请添加图片描述

完整代码如下

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return intervals
        
        # 排序
        intervals.sort(key=lambda x:x[0])

        # 结果集
        result = []
        result.append(intervals[0])

        for i in range(1, len(intervals)):
            last = result[-1]  # 取出结果集的最后一个区间
            if last[1] >= intervals[i][0]:
                result[-1] = [last[0], max(last[1], intervals[i][1])]  # last的第0个维度不变,更新第1个维度
            else:
                result.append(intervals[i])
        return result
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-08-19 19:31:09  更:2022-08-19 19:31:22 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 21:40:54-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码