代码随想录day35【贪心算法】 柠檬水找零 根据身高重建队列 用最少数量的箭引爆气球

柠檬水找零

力扣题目链接
自己的思路：

1. 用map存起来5，10，20的个数
2. 遇到20找零的情况有两种。未对两种情况的优先级进行分析。

改进：

1. 直接用变量记录5，10 的个数，20 不用记录，因为不会花掉。
2. 遇到20找零的情况有两种。应先用掉10，5，以保留最多的5，用于找零10及20.

//自己写的

var lemonadeChange = function(bills) {
    let map=new Map()

    for(let i in bills){
        if(bills[i] === 5){
            map.set(5,map.get(5)? (map.get(5)+1) : 1)
        }else if(bills[i]===10){
            if(map.get(5)>=1){
                map.set(5,map.get(5)-1)
                map.set(10,map.get(10)? (map.get(10)+1) : 1)
            }else{
                return false
            }
        }else if(bills[i]===20){
            if(map.get(10)>=1 && map.get(5)>=1){
                map.set(10,map.get(10)-1)
                map.set(5,map.get(5)-1)
                map.set(20,map.get(20)? (map.get(20)+1): 1)
            }else if(map.get(5)>=3){
                map.set(5,map.get(5)-3)
                map.set(20,map.get(20)? (map.get(20)+1): 1)
            }else{
                return false
            }
        }
    }
    return true
};

//参考

var lemonadeChange = function(bills) {
    let five=0,ten=0

    for(let i in bills){
        if(bills[i] === 5){
            five++
        }else if(bills[i]===10){
            if(five>=1){
                five--
                ten++
            }else{
                return false
            }
        }else if(bills[i]===20){
            if(ten>=1 && five >=1){
                ten--
                five--
            }else if(five>=3){
                five -= 3
            }else{
                return false
            }
        }
    }
    return true
};

根据身高重建队列

力扣题目链接
思路：
先按照身高排序(身高相同k小的在前面！注意），再根据k 插入身高的排序结果中。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

var reconstructQueue = function(people) {
    people.sort((a, b ) => {
        if(b[0] !== a[0]) {
            return b[0] - a[0]
        } else {
            return a[1] - b[1]
        }
        
    })

    let queue=[]
    for(let i in people){
        let pos = people[i][1]
        queue.splice(pos,0,people[i])
    }
    return queue
};

用最少数量的箭引爆气球

力扣题目链接
自己的分析不足之处：未更新右边界，用以判断下一个气球是否能覆盖。

参考思路：
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

var findMinArrowShots = function(points) {
    points.sort((a,b)=>{
            return a[0]-b[0]
    })


    let res=1
    for(let i=0;i<points.length-1;i++){
        if(points[i+1][0]>points[i][1]){
            res++
        }else{
            points[i+1][1]= Math.min(points[i][1],points[i+1][1]) //注意这段代码。。自己没写出来
        }
    }
    return res
};