算法训练day37 LeetCode860.406.452.

860.柠檬水找零

题目

860. 柠檬水找零 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

5：收五元
10：收十元，返五元
20：优先还十元+五元；否则还五元*3

class Solution
{
public:
    bool lemonadeChange(vector<int> &bills)
    {
        int five = 0, ten = 0, twenty = 0;
        for (int bill : bills)
        {
            if (bill == 5)
                five++;
            if (bill == 10)
            {
                if (five <= 0)
                    return false;
                ten++;
                five--;
            }
            if (bill == 20)
            {
                if (five > 0 && ten > 0)
                {
                    five--;
                    ten--;
                }
                else if (five >= 3)
                {
                    five -= 3;
                }
                else
                    return false;
            }
        }
        return true;
    }
};

406.根据身高重建队列

题目

406. 根据身高重建队列 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

按身高排序，接着由大到小插入到新的位置（que
- 可以保证数据a插入que前，que中数据均大于等于a ----->a插入的位置符合要求
- 使用链表，提高运行速度

class Solution
{
public:
    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;
        for (int i = 0; i < people.size(); i++)
        {
            int position = people[i][1];
            std::list<vector<int>>::iterator it = que.begin();//	这一行将迭代器it初始化为que列表的开始位置。
            while (position--)	//这个循环通过position的值将迭代器it移动
            {
                it++;
            }
            que.insert(it, people[i]);	//在找到列表中的正确位置后，将当前人插入到该位置。
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};