算法训练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());
      }
  };
  

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