JLUVicent

860柠檬水找零&406根据身高重建队列&452用最少数量的箭引爆气球

 
  • 2023年 03月21日
  • 0 阅读

day35

860.柠檬水找零

题目链接：860. 柠檬水找零

解题思路：自己做直接AC了

针对遇到5，10，20时候的情况分类讨论，对应变量做加或者减操作即可

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int num5 = 0;
        int num10 = 0;
        for( int i = 0; i < bills.size(); i++){
            if( bills[i] == 5 ){
                num5 +=1;
            }
            else if( bills[i] == 10){
                num10 += 1;
                num5 -= 1;
            }
            else if( bills[i] == 20 ){
                // num10 -= 1;
                if(num10 > 0){
                    num10 -= 1;
                    num5 -= 1;
                }
                else{
                    num5 -= 3;
                }
            }
            if( num5 < 0 || num10 < 0){
                return false;
            }
        }
        return true;

    }
};

406.根据身高重建队列

题目链接：406. 根据身高重建队列

解题思路：参考 视频

本题有两个维度，h和k，一定要先确定一个维度，在确定另外一个维度

先排身高再排数量

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

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

class Solution {
public:

    // 定义cmp函数需要加上static
    static bool cmp( const vector<int>& a, const vector<int>& b){
        if( a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort( people.begin(),people.end(),cmp);
        // vector<vector<int>> que;
        // 注意list插入和vector插入的区别
        list<vector<int>> que;
        for( int i = 0; i < people.size(); i++){
            int position = people[i][1];
            // que.insert( que.begin() + position,people[i]);
            std::list<vector<int>>::iterator it = que.begin();
            while( position--){
                it++;   //寻找插入位置
            }
            que.insert(it,people[i]);
        }
        return vector<vector<int>>(que.begin(),que.end());
        
    }
};
// list插入效率更高

贪心算法：根据身高重建队列（续集） 针对vector和list讲解

参考

vector和list的区别：插入使用list效率较高

// vector插入
vector<vector<int>> que;
que.insert( que.begin() + position,people[i]);
// list插入
std::list<vector<int>>::iterator it = que.begin();
while( position--){
    it++;   //寻找插入位置
}
que.insert(it,people[i]);
vector<vector<int>>(que.begin(),que.end());

452.用最少数量的箭引爆气球

题目链接：452. 用最少数量的箭引爆气球

解题思路：参考 视频

452.用最少数量的箭引爆气球

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

class Solution {
public:
    static bool cmp( vector<int>& a, vector<int>& b){
        if( a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if( points.size() == 0) return 0;
        sort( points.begin(),points.end(),cmp);
        int result = 1;
        for( int i = 1; i < points.size(); i++){
            if( points[i][0] > points[i-1][1]){
                result++;
            }else{
                points[i][1] = min(points[i][1],points[i-1][1]);
            }
        }
        return result;
    }
};
搜索