最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

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

来源：博客园

LeetCode860. 柠檬水找零

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

独上高楼，望尽天涯路

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


(资料图片仅供参考)

class Solution {public:    bool lemonadeChange(vector& 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 a, vector b) {        return (a[0] > b[0]) || (a[0] == b[0] && a[1] < b[1]);    }    vector> reconstructQueue(vector>& people) {        sort(people.begin(), people.end(), cmp);        for (int i = 0; i < people.size(); i++) {            if (people[i][1] < i) {                vector 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& a, const vector& b) {        if (a[0] == b[0]) return a[1] < b[1];        return a[0] > b[0];    }    vector> reconstructQueue(vector>& people) {        sort (people.begin(), people.end(), cmp);        list> que; // list底层是链表实现，插入效率比vector高的多        for (int i = 0; i < people.size(); i++) {            int position = people[i][1]; // 插入到下标为position的位置            std::list>::iterator it = que.begin();            while (position--) { // 寻找在插入位置                it++;            }            que.insert(it, people[i]);        }        return vector>(que.begin(), que.end());    }};

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

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

独上高楼，望尽天涯

没有很好的思路。

慕然回首，灯火阑珊

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

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

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

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

class Solution {public:    static bool cmp(const vector& a, const vector& b) {        return a[0] < b[0];    }    int findMinArrowShots(vector>& 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;    }};

关键词： 独上高楼 灯火阑珊 灯火阑珊处