制作介绍的网站模板,同学录wordpress,红桥网站建设,企业品牌网站建设费用LeetCode 452.用最少数量的箭引爆气球#xff1a;
文章链接 题目链接#xff1a;452.用最少数量的箭引爆气球
思路#xff1a;
气球的区间有重叠部分#xff0c;只要弓箭从重叠部分射出来#xff0c;那么就能减少所使用的弓箭数 **局部最优#xff1a;**只要有重叠部分…LeetCode 452.用最少数量的箭引爆气球
文章链接 题目链接452.用最少数量的箭引爆气球
思路
气球的区间有重叠部分只要弓箭从重叠部分射出来那么就能减少所使用的弓箭数 **局部最优**只要有重叠部分就从重叠部分射出弓箭 全局最优引爆所有气球所必须射出的最小弓箭数。
① 要求重叠部分最好先将points数组排序按start或end都可以此处按照start顺序排序。 ② 因为只需要弓箭的数目因此不需要记录有哪些重叠区间只需要变量minRight记录重叠气球最小右边界和count记录弓箭数即可。 ③ 从前向后遍历如果当前气球与之前气球区间有重叠部分即points[i][0] minRight那么更新minRight如果没有重叠部分重置minRight为points[i][1]重新记录重叠气球最小右边界并增加一支弓箭
class Solution:def findMinArrowShots(self, points: List[List[int]]) - int:if len(points) 0:return 0points.sort(keylambda x: x[0])count 1 # points不为空至少需要一支箭minRight points[0][1] # 记录最小右边界因为有重叠部分右边界只会减小for point in points:if point[0] minRight: # 没挨着minRight point[1] # 重置minRightcount 1 # 增加一支箭else:minRight min(minRight, point[1]) # 得到最小右边界return count
不使用minRight记录使用points[i - 1][1]记录最小右边界class Solution:def findMinArrowShots(self, points: List[List[int]]) - int:if len(points) 0:return 0points.sort(keylambda x: x[0]) # 排序count 1 # points不为空至少需要一支弓箭for i in range(1, len(points)):if points[i][0] points[i - 1][1]: # 当前气球区间与前一个没有挨着count 1else:points[i][1] min(points[i - 1][1], points[i][1]) # 更新最小右边界return count感悟
只记录数量的话函数实现过程中不用记录所有重叠区间使用一个变量记录当前重叠气球最小右边界即可因为排序后如果当前气球与前面不重叠的话原来的重叠气球部分与之后的不会重叠了那么就只需要记录新的即可 LeetCode 435.无重叠区间
文章链接 题目链接435.无重叠区间
思路:
一般来说多个区间重叠有两种情况以三个区间重叠为例 1第三个区间的重叠部分在前两个区间的重叠部分中。 那么需要删除其中两个区间才能使区间不重叠 2第三个区间的重叠部分不在前两个区间的重叠部分中。 那么只需要删除中间的区间就能使得两个区间不重叠。 如果采用的是两个区间重叠后保留的是重叠部分再与后面的区间进行判断是否重叠那么可以统一上面两种情况第二种情况到第三个区间时会判断不重叠。
记录重叠部分 那么我们首先对区间集合按照左边界进行排序同时使用minRight记录重叠区间的最小右边界count记录重叠区间数。
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:if len(intervals) 0:return 0intervals.sort(keylambda x: x[0])count 0 # 记录重叠的区间数minRight intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] minRight:minRight intervals[i][1]else:count 1minRight min(minRight, intervals[i][1])return count
记录不重叠部分 其实记录不重叠部分可以对上面的代码进行修改count 1从else改成if 同时初始化为1即可。 还有一种方法因为判断是否重叠采用的是重叠部分最小右边界因此是否可以直接对数组按照右边界进行排序如果后面的区间与前面不重叠重置最小右边界否则不进行操作因为按照右边界排序前面重叠部分第一个一定是最小右边界
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:if len(intervals) 0:return 0intervals.sort(keylambda x:x[1]) # 按右边界进行排序count 1 # 记录非重叠区间数minRight intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] minRight: # 不重叠count 1minRight intervals[i][1]return len(intervals) - count感悟
判断是否重叠采用的是重叠最小右边界n个区间是否重叠是看前面n - 1个的重叠部分是否在第n个区间中出现即上图情况1。使用最小右边界进行判断可以直接对数组按照右边界进行排序从而只需要在不重叠时重置minRight即可。 LeetCode 763.划分字母区间
文章链接 题目链接763.划分字母区间
思路
贪心1可能不算贪心 ① 首先求出字符串中每个字符的最远位置用数组 ② 遍历字符串同时更新当前遍历片段的最远位置即其中字符最远位置的最远位置如果当前位置为最远位置表明到达切分点对字符串进行切分后继续遍历下一片段
class Solution:def partitionLabels(self, s: str) - List[int]:if len(s) 0:return []hashLetter [-1] * 26 # 保存字符的最远下标for i in range(len(s)):hashLetter[ord(s[i]) - ord(a)] iresult []start 0 # 当前片段开始maxIndex 0 # 当前片段中字符中最远位置的最远位置即当前片段结束for i in range(len(s)):# 更新最远位置if hashLetter[ord(s[i]) - ord(a)] maxIndex:maxIndex hashLetter[ord(s[i]) - ord(a)]if maxIndex i: # 到达最远位置即片段结束result.append(i - start 1) # 双闭区间# 重置start等为下一个片段start i 1maxIndex 0return result贪心2 类似前面引爆气球和无重叠区间的思路。 ① 记录字符串中每个字符的开始位置和结束位置从而得到一系列区间 ② 首先对区间按照左边界进行排序然后对重叠的区间进行合并此处判断多个区间是否重叠包含如下两种情况 1第三个区间的重叠部分在前两个区间的重叠部分中。 2第三个区间的重叠部分不在前两个区间的重叠部分中。 ③ 从而使用最大右边界记录当前重叠区间的右边界。如果下一个区间没有和当前区间重叠说明重叠结束应当划分片段。 需要注意的是 1记录字符的开始和结束位置记录开始位置的同时要记录结束位置因为会出现字符只出现一次的情况 2前面记录字符的开始和结束采用的是数组字符到数组下标的映射为ord(x) - ord(‘a’)因此在排序区间数组前需要清理掉字符串中没有用到的字符。 3前面几题只需要记录数量此处需要划分区间因此需要start记录区间的开始 4for循环遍历完成后还有最后一个区间没有加入result中
class Solution:def countLetter(self, s):# 记录字符串中每个字符的开始和结束位置letterSE [[-1, -1] for _ in range(26)]for i in range(len(s)):if letterSE[ord(s[i]) - ord(a)][0] -1:letterSE[ord(s[i]) - ord(a)][0] iletterSE[ord(s[i]) - ord(a)][1] i# 去除letterSE的s不存在的字符letters []for i in range(len(letterSE)):if letterSE[i][0] ! -1:letters.append(letterSE[i])return lettersdef partitionLabels(self, s: str) - List[int]:if len(s) 0:return 0letters self.countLetter(s) # 得到各个字符的区间letters.sort(keylambda x: x[0]) # 按照左边界排序# 字符串中多个字符重叠区间的最大值即为所划分区间result []start 0maxRight letters[0][1] # 这里是求最大右边界for i in range(1, len(letters)):if letters[i][0] maxRight: # 没挨着result.append(maxRight - start 1)start letters[i][0]maxRight max(letters[i][1], maxRight)# 结尾一个result.append(maxRight - start 1)return result 学习收获
区间是否重叠以及如何求存在重叠部分的重叠区间数和非重叠区间数以及合并区间
