天津開發(fā)網(wǎng)站公司免費(fèi)b站推廣軟件
貪心
1、435. 無重疊區(qū)間
題目：
給定一個(gè)區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 。
思路：
- 貪心，重疊個(gè)數(shù)，和射氣球一樣,重疊區(qū)間
func eraseOverlapIntervals(intervals [][]int) int {// 代碼一刷sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := 0for i:=1; i<len(intervals); i++ {if intervals[i][0] < intervals[i-1][1] {res++intervals[i][1] = min(intervals[i][1], intervals[i-1][1])}}return res
}
func min(a,b int) int {if a>b {return b};return a}
2、763. 劃分字母區(qū)間
題目：
輸入：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; i<size; i++ {map1[s[i]] = i}for i:=0; i<size; i++ {right = max(right, map1[s[i]])if i==right {res = append(res, right-left+1)left = i+1}}return res
}
func max(a,b int)int{if a>b {return a}; return b}
3、56. 合并區(qū)間
題目：
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
思路：
- 簡(jiǎn)單，貪心,區(qū)間問題
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; i<len(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 a>b {return a}; return b}