题目一

leetcode:452

代码与解析

给定二维空间, 一个二维数组
[[10,16],[2,8],[1,6],[7,12]]里每一个数组,代表的是横坐标起点,终点

类似这样,求最少的射箭数
思路:

  • 先排序,让这些区间按顺序站好

  • 遍历,看当前区间右边界和下一个区间左边界大小关系,大于则res++

  • 否则,就要更新最小右边界!!!!!!
    详见可以看carl大佬的思路

    有一点需要注意: res初始为1

    这里的关键是 判断左右边界大小和更新边界points[i][1] = min(points[i-1][1], points[i][1])

func findMinArrowShots(points [][]int) int {
    // 请注意
    res := 1
    // 排序
    sort.Slice(points, func(i, j int)bool{
        return points[i][0]<points[j][0]
    })
    for i:=1;i<len(points);i++{
        // 看当前区间右边界和下一个区间左边界大小关系,大于则res++
        if points[i-1][1]<points[i][0]{
            res++
        }else{
            // 更新最小右边界
            points[i][1] = min(points[i-1][1], points[i][1])
        }
    }
    return res
}
func min(i, j int)int{
    if i>j{
        return j
    }else{
        return i
    }
}

题目二

leetcode:435

代码与解析

这道题和上一道题有异曲同工之妙,
这个也是判断左右区间
甚至比上一道简单,只需要找到相应区间,

上一道是找到不重合的左右边界res++
这一道是找到重合的左右边界res++

func eraseOverlapIntervals(intervals [][]int) int {
    res:= 0
    sort.Slice(intervals, func(i, j int)bool{
        return intervals[i][0]<=intervals[j][0]
    })
    info0, info1 := []int{}, []int{}
    for i:=1;i<len(intervals);i++{
        info0 = intervals[i-1]
        info1 = intervals[i]
        // 判断当前区间右边界,和下一区间左边界大小。
        // 如果重复,更新最小右边界,res++
        if info0[1] > info1[0]{
            intervals[i][1] = min(intervals[i-1][1], intervals[i][1])
            res++
        }
    }
    return res
}
func min(i, j int)int{
    if i>j{
        return j
    }else{
        return i
    }
}

题目三

leetcode:56

代码与解析

这道题和上面两道也很像,
上面两道是更新最小右边界
这道题是更新最大右边界,并顺势去掉不符合的数组
详解可以看下面代码注释或者carl博客

这里的关键也是 判断左右边界大小和更新边界points[i][1] = min(points[i-1][1], points[i][1])
另外索引i要– 否则索引越界

func merge(intervals [][]int) [][]int {
    //先从小到大排序
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][0]<intervals[j][0]
    })
    //再弄重复的
    for i:=0;i<len(intervals)-1;i++{
        // 当前右边界intervals[i][1]和下一区间左边界intervals[i+1][0]比较
        // 这种情况相当于[1,4] [2,5]
        if intervals[i][1]>=intervals[i+1][0]{
            // 更新区间右边界最大值
            intervals[i][1]=max(intervals[i][1],intervals[i+1][1])//赋值最大值
            // 删除下一个区间元素,因为此时当前区间右边界已经变了
            intervals=append(intervals[:i+1],intervals[i+2:]...)
            i--
        }
    }
    return intervals
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号