商业网站开发实训心得体会范文,网站设计网站设计网站设计,河北工商注册网入口,wordpress右边小工具贪心
1、435. 无重叠区间
题目#xff1a; 给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。
思路#xff1a;
贪心#xff0c;重叠个数#xff0c;和射气球一样,重叠区间…贪心
1、435. 无重叠区间
题目 给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。
思路
贪心重叠个数和射气球一样,重叠区间
func eraseOverlapIntervals(intervals [][]int) int {// 代码一刷sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] intervals[j][0]})res : 0for i:1; ilen(intervals); i {if intervals[i][0] intervals[i-1][1] {resintervals[i][1] min(intervals[i][1], intervals[i-1][1])}}return res
}
func min(a,b int) int {if ab {return b};return a}2、763. 划分字母区间
题目 输入s “ababcbacadefegdehijhklij” 输出[9,7,8]
思路
很有意思贪心就是记录最大值
func partitionLabels(s string) []int {// 代码一size, left, right : len(s), 0, 0res : []int{}map1 : make(map[byte]int, 26)for i:0; isize; i {map1[s[i]] i}for i:0; isize; i {right max(right, map1[s[i]])if iright {res append(res, right-left1)left i1}}return res
}
func max(a,b int)int{if ab {return a}; return b}3、56. 合并区间
题目 输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
思路
简单贪心,区间问题
func merge(intervals [][]int) [][]int {// 代码一刷sort.Slice(intervals, func(i, j int) bool {return intervals[i][0]intervals[j][0]})res : make([][]int, 0)left, right : intervals[0][0], intervals[0][1]for i:1; ilen(intervals); i {if right intervals[i][0] {res append(res, []int{left, right})left, right intervals[i][0], intervals[i][1]} else {right max(right, intervals[i][1])}}res append(res, []int{left, right})return res
}
func max(a, b int)int{if ab {return a}; return b}
