虚拟主机网站建设步骤?,青海省住房和城乡建设厅 网站首页,网站前端设计要做什么,机关作风建设网站文章目录 435. 无重叠区间思路思路代码困难 763.划分字母区间思路官方题解代码困难 56. 合并区间思路思路代码 今日收获 435. 无重叠区间
思路
重叠问题都需要先排好序#xff0c;再贪心
思路代码
func eraseOverlapIntervals(intervals [][]int) int {sort.Slice(interva… 文章目录 435. 无重叠区间思路思路代码困难 763.划分字母区间思路官方题解代码困难 56. 合并区间思路思路代码 今日收获 435. 无重叠区间
思路
重叠问题都需要先排好序再贪心
思路代码
func eraseOverlapIntervals(intervals [][]int) int {sort.Slice(intervals,func(i,j int)bool{return intervals[i][1]intervals[j][1]})count:1end:intervals[0][1]for i:1;ilen(intervals);i{if endintervals[i][0]{endintervals[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. 合并区间
思路
与前面类似但又不同
思路代码
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;ilen(intervals);i{if rightintervals[i][0]{resappend(res,[]int{left,right})leftintervals[i][0]rightintervals[i][1]}else{rightmax(right,intervals[i][1])}}resappend(res,[]int{left,right})return res}func max(i,j int)int{if ij{return i}return j
}今日收获
重叠问题大致分两类 一类是重叠区间问题箭射气球 一类是合并区间问题 做法类似但是处理的逻辑不太相同左右区间排序的选择也有不同。
