代码随想录算法训练营第35天 | 860.柠檬水找零, 406.根据身高重建队列, 452.用最少数量的箭引爆气球

860.柠檬水找零

代码随想录链接

题目

LeetCode-860.柠檬水找零

一杯柠檬水售价5元, 顾客们会给5元, 10元, 20元的钱, 按照先后顺序组成一个数组, 没有额外零钱, 求能否完成找零任务.

自己的想法

统计一下5元和10元的钱的数量, 遇到5元就只统计, 遇到10元需要统计并试图使用一张5元来找零, 找零不成功则返回false, 遇到20元时不用统计, 先试图用1张10元和1张5元来找零, 不成功的话再使用3张5元找零, 仍然不成功的话则找零失败.

题解

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int count5 = 0, count10 = 0;
        for (int b : bills) {   // 遍历账单
            if (b == 5) count5++;   // 统计5元数量
            if (b == 10) {          // 统计10元数量
                count10++;
                if (count5) count5--;
                else return false;
            }
            if (b == 20) {          // 遇到20元时
                if (count10) {      // 先试图用1张10元和1张5元找零
                    if (count5) {
                        count10--;
                        count5--;
                        continue;   // 找零成功, 则继续下一个账单
                    }
                }
                if (count5 >= 3) count5 -=3;    // 试图用三张5元找零
                else return false;
            }
        }
        return true;
    }
};

406.根据身高重建队列

代码随想录链接

题目

LeetCode-406.根据身高重建队列

针对一群人的身高的队列给定一个乱序数组, 数组中每个元素包含两个元素, 其中第一位元素表示其身高, 第二位元素表示队伍前面有多少身高大于等于自己的人, 返回表示实际队伍的数组.

自己的想法

两个维度, 和昨天做的根据评分来给糖果的题目有点像, 同样应该是先集中考虑一个维度再考虑另一个维度.

先根据前面有几个人不比自己低来排序的话, 排不出来什么, 所以应该先根据身高排序.

先根据身高排序, 由于第二个维度是前面不比自己低的人有几个, 所以身高就按照从大到小排, 排序完成之后, 再遍历排完序的数组, 根据第二个维度的值插入到相应位置即可.

题解

class Solution {
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];
}
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);    // 对身高排序
        list<vector<int>> result;                   // 使用list降低插入时的时间复杂度
        for (int i = 0; i < people.size(); i++) {   // 遍历排序后的数组, 按照第二个维度插入元素
            int pos = people[i][1];
            auto it = result.begin();
            while (pos--) it++;
            result.insert(it, people[i]);
        }
        return vector<vector<int>>(result.begin(), result.end());
    }
};

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

代码随想录链接

题目

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

给定一组气球的在x轴上的投影范围, 计算至少垂直于X轴发射几支箭才能使得所有气球爆炸.

自己的想法

要计算至少需要多少支箭才能引爆所有气球, 就需要让一支箭尽可能多地引爆多个气球. 对于气球给定的范围, 我们可以将这些气球从左往右进行一个排序, 将有重叠的气球的右边界修整到一致, 使得这些气球能被一支箭引爆.

题解

class Solution {
static bool cmp(const vector<int> &a, const vector<int> &b) {
    return a[0] < b[0];
}
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;
        int result = 1; // 若气球数量不为0, 则至少需要一支箭
        sort(points.begin(), points.end(), cmp);    // 将气球按照左侧索引进行排序
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) result++;  // 如果相邻两个气球没有重复的, 则需要的箭数要+1
            else points[i][1] = min(points[i - 1][1], points[i][1]);    // 如果有重复的部分, 则将第二个气球的右边界收缩到第一个气球的右边界, 方便对于后序气球的判断
            /**
             * 那要是有三个气球有重叠部分呢?
             * 这样在第三个气球与第二个气球对比时, 第三个气球的右边界也会修正, 代表这些气球已经被对齐的目的气球的同一支箭来引爆
             */
        }
        return result;
    }
};