贪心算法part5

2023-06-21 06:36| 来源: 网络整理| 查看: 265

文章目录 435. 无重叠区间思路思路代码困难 763.划分字母区间思路官方题解代码困难 56. 合并区间思路思路代码今日收获

435. 无重叠区间思路

重叠问题都需要先排好序，再贪心

思路代码 func eraseOverlapIntervals(intervals [][]int) int { sort.Slice(intervals,func(i,j int)bool{ return intervals[i][1] 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 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 res:=[][]int{} sort.Slice(intervals,func (i,j int)bool{ return 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 } 今日收获

重叠问题大致分两类一类是重叠区间问题（箭射气球）一类是合并区间问题做法类似但是处理的逻辑不太相同，左右区间排序的选择也有不同。

【本文地址】

贪心算法part5

贪心算法part5

今日新闻

推荐新闻