【算法训练营day35】LeetCode860. 柠檬水找零 LeetCode406. 根据身高重建队列 LeetCode452. 用最少数量的箭引爆气球

LeetCode860. 柠檬水找零

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

独上高楼，望尽天涯路

本来以为只想到了最笨的方法，即讨论所有情况。

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

慕然回首，灯火阑珊处

结果没想到题解也是这么做的。

LeetCode406. 根据身高重建队列

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

独上高楼，望尽天涯

这次终于思路对了！！！并且代码ac！！！

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        return (a[0] > b[0]) || (a[0] == b[0] && a[1] < b[1]);
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        for (int i = 0; i < people.size(); i++) {
            if (people[i][1] < i) {
                vector<int> temp = people[i];
                people.erase(people.begin() + i);
                people.insert(people.begin() + temp[1], temp);
            }
        }
        return people;
    }
};

慕然回首，灯火阑珊

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

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

使用vector比较费时，使用list（底层是链表实现）新创建一个数组作为输出会省时不少。

class Solution {
public:
    // 身高从大到小排（身高相同k小的站前面）
    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);
        list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 插入到下标为position的位置
            std::list<vector<int>>::iterator it = que.begin();
            while (position--) { // 寻找在插入位置
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

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

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

独上高楼，望尽天涯

没有很好的思路。

慕然回首，灯火阑珊

这类问题被称作重叠区间问题。

为了让气球尽可能的重叠，需要对数组进行排序。

从前向后遍历遇到重叠的气球了怎么办？

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        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]) { // 气球i和气球i-1不挨着
                result++; // 增加一支箭
            }
            else { // 气球i和气球i-1挨着
                points[i][1] = min(points[i][1], points[i - 1][1]); // 更新重叠气球的最小右边界
            }

        }
        return result;
    }
};