【leetcode】【2022/10/19】1700. 无法吃午餐的学生数量

问题描述：

• 学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。
  • 所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
  • 餐厅里三明治的数量与学生的数量相同。
• 所有三明治都放在一个栈里，每一轮：
  • 如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列。
  • 否则，这名学生会放弃这个三明治并回到队列的尾部。
  • 这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
• 给你两个整数数组 students 和 sandwiches，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部），students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）
  • 请你返回无法吃午餐的学生数量。

核心思路：

• 该题可以直接暴力模拟，也可以用贪心策略。
  • 暴力模拟就是将 students 数组存入队列 q 中，一次遍历就把队列中所有元素访问一次，只要某一次遍历后队列的大小不变就认为循环结束，否则就一直循环遍历。【其余行为就是在模拟题目，不断取出 q 的头部并与 sandwiches 数组的头部比较】
  • 贪心策略其实也比较简单，统计 students 中 1 和 0 的个数，而一次遍历 sandwiches 就可以确定结果；遍历停止的条件就是 sandwiches 的头部元素的剩余学生个数为零，例如当前头部元素为 1，而剩余学生中 1 的个数为零，则此时剩余所有学生都不喜欢栈顶的三明治。

代码实现：

• 模拟解法代码实现如下：

  class Solution
  {
  public:
      int countStudents(vector<int>& students, vector<int>& sandwiches)
      {
          queue<int> q;
          for(int num : students) q.push(num);
          int idx = 0;
          while(1)
          {
              int sz = q.size();
              for(int i = 0; i < sz; ++i)
              {
                  int tmp = q.front(); q.pop();
                  if(tmp == sandwiches[idx]) ++idx;
                  else q.push(tmp);
              }
              if(q.size() == sz) return sz;
          }
          return 0;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22