代码随想录 day31|| 56 合并区间，738 单调递增数字，968 监控二叉树

56 合并区间

func merge(intervals [][]int) [][]int {
	// 思路先排序，然后按照后一个左区间和前一个右区间进行对比判断是否重叠，重叠扩充右区间
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0]{
			return intervals[i][1] < intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})

	var res [][]int
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] <= intervals[i-1][1] {
			// 后面左边界对比前一个右边界，小于就是有重叠
			intervals[i][0] = min(intervals[i-1][0], intervals[i][0])
			intervals[i][1] = max(intervals[i-1][1], intervals[i][1])
		}else {
			// 如果不重叠，就将前一个元素加入返回值
			res = append(res, intervals[i-1])
		}
	}
	res = append(res, intervals[len(intervals) - 1])
	return res
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
func min(x, y int )int {
	if x < y {
		return x
	}
	return y
}

func merge(intervals [][]int) [][]int {
	// 思路先排序，然后按照后一个左区间和前一个右区间进行对比判断是否重叠，重叠扩充右区间
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0]{
			return intervals[i][1] < intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})

	var res [][]int
	res = append(res, intervals[0])
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] <= res[len(res) - 1][1] {
			// 后面左边界对比结果集中的合并区间小，小于就是有重叠
			res[len(res) - 1][0] = min(res[len(res) - 1][0], intervals[i][0])
			res[len(res) - 1][1] = max(res[len(res) - 1][1], intervals[i][1])
		}else {
			// 如果不重叠，就将前一个元素加入返回值
			res = append(res, intervals[i])
		}
	}
	return res
}

// 直接在结果集上面操作

738 单调递增数字

func monotoneIncreasingDigits(n int) int {
	// 思路，操作办法，从后往前遍历，如果新的数字大于之前数字，那么新数字-1. 后面数字都变成9
	if n <= 9 {
		return n
	}


	var res []int
	var next, cur int
	next = n % 10 // 初始化最后一位
	n = n / 10
	res = append([]int{next}, res...)
	for n != 0 {
		cur = n % 10
		if cur > next {
			fill(res)
			cur--
			res = append([]int{cur}, res...)
		}else{
			res = append([]int{cur}, res...)
		}
		next = cur
		n = n / 10
	}
	fmt.Println(res)
	var mix int
	for _, v := range res {
		mix = mix * 10 + v
	}

	return mix
}

func fill(nums []int) {
	for idx, _ := range nums{
		nums[idx] = 9
	}
}

968 监控二叉树

待定