435. 无重叠区间
思路
重叠问题都需要先排好序,再贪心
思路代码
func eraseOverlapIntervals(intervals [][]int) int {
sort.Slice(intervals,func(i,j int)bool{
return intervals[i][1]<intervals[j][1]
})
count:=1
end:=intervals[0][1]
for i:=1;i<len(intervals);i++{
if end<=intervals[i][0]{
end=intervals[i][1]
count++
}
}
return len(intervals)-count
}
困难
搞清楚左右区间,重叠的条件。
要找出最少删除的数量,也就是找出重叠空间的数量,然后用长度减去即可。
763.划分字母区间
思路
这里提供一种与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。
统计字符串中所有字符的起始和结束位置,记录这些区间(实际上也就是435.无重叠区间 (opens new window)题目里的输入),将区间按左边界从小到大排序,找到边界将区间划分成组,互不重叠。找到的边界就是答案。
官方题解
一想到分割字符串就想到了回溯,但本题其实不用回溯去暴力搜索。
题目要求同一字母最多出现在一个片段中,那么如何把同一个字母的都圈在同一个区间里呢?
如果没有接触过这种题目的话,还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。
可以分为如下两步:
统计每一个字符最后出现的位置
从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
代码
func partitionLabels(s string) []int {
var res []int;
var marks [26]int;
size, left, right := len(s), 0, 0;
for i := 0; i < size; i++ {
marks[s[i] - 'a'] = i;
}
for i := 0; i < size; i++ {
right = max(right, marks[s[i] - 'a']);
if i == right {
res = append(res, right - left + 1);
left = i + 1;
}
}
return res;
}
func max(a, b int) int {
if a < b {
a = b;
}
return a;
}
困难
将字符串转换为每个字符的起始位置,终止位置
56. 合并区间
思路
与前面类似但又不同文章来源:https://www.toymoban.com/news/detail-489413.html
思路代码
func merge(intervals [][]int) [][]int {
res:=[][]int{}
sort.Slice(intervals,func (i,j int)bool{
return intervals[i][0]<intervals[j][0]})
left,right:=intervals[0][0],intervals[0][1]
for i:=1;i<len(intervals);i++{
if right<intervals[i][0]{
res=append(res,[]int{left,right})
left=intervals[i][0]
right=intervals[i][1]
}else{
right=max(right,intervals[i][1])
}
}
res=append(res,[]int{left,right})
return res
}
func max(i,j int)int{
if i>j{
return i
}
return j
}
今日收获
重叠问题大致分两类
一类是重叠区间问题(箭射气球)
一类是合并区间问题
做法类似但是处理的逻辑不太相同,左右区间排序的选择也有不同。文章来源地址https://www.toymoban.com/news/detail-489413.html
到了这里,关于贪心算法part5 | ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!