【栈】无法吃午餐的学生数量(leetcode1700)

叁歲伎倆 2022-10-18 12:54 67阅读 0赞

一、题目

  1. 学校的自助午餐提供圆形和方形的三明治,分别用数字 0 1 表示。所有学生站在一个队列里,每个学生要么喜欢圆形的要么喜欢方形的。
  2. 餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 里,每一轮:
  3. 如果队列最前面的学生 喜欢 栈顶的三明治,那么会 拿走它 并离开队列。
  4. 否则,这名学生会 放弃这个三明治 并回到队列的尾部。
  5. 这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
  6. 给你两个整数数组 students sandwiches ,其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型(i = 0 是栈的顶部), students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好(j = 0 是队列的最开始位置)。请你返回无法吃午餐的学生数量。
  7. 来源:力扣(LeetCode
  8. 链接:https://leetcode-cn.com/problems/number-of-students-unable-to-eat-lunch
  9. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

在这里插入图片描述

二、分析

对于本题,需要先理解的是:三明治的顺序是无法改变的,但是学生队列的顺序是可以改变的。所以基本操作是:

  • 将学生数组和三明治数组分别转换成用队列(Qstudent)和栈(Ssandwiches)存放。
  • 每次让队首的学生 Qstudent.front() 和栈顶的三明治 Ssandwiches.top() 比较。如果相等,则同时pop()出一个元素;如果不相等,则将Qstudent队首的元素放到队列末尾。
  • 当连续出现当前Qstudent.size()次数不相同情况时,说明学生即使轮换一圈,也无法领到满意的三明治,所以退出循环;或者当学生人数为0 时,也要退出循环。最后返回的Qstudent.size()即时剩余的没吃到三明治的学生人数

三、题解

C++实现如下:

  1. class Solution {
  2. public:
  3. int countStudents(vector<int>& students, vector<int>& sandwiches) {
  4. queue<int> Qstudent;
  5. stack<int> Ssandwiches;
  6. for(int num:students) Qstudent.push(num); //将students重新存入队列里
  7. reverse(sandwiches.begin(), sandwiches.end());
  8. for(int num:sandwiches) Ssandwiches.push(num); //将sandwiches重新存入栈中
  9. int cunt = 0;//记录学生连续没有领到三明治的次数
  10. while(1)
  11. {
  12. if(Qstudent.front()==Ssandwiches.top())
  13. {
  14. Qstudent.pop();
  15. Ssandwiches.pop();
  16. cunt = 0;
  17. }
  18. else
  19. {
  20. Qstudent.push(Qstudent.front());
  21. Qstudent.pop();
  22. cunt += 1;
  23. }
  24. // 当cunt超过剩余的学生人数(轮完一周),则说明剩下的学生不再可能领到三明治
  25. if(cunt>=Qstudent.size() || Qstudent.size()==0)
  26. break;
  27. }
  28. return Qstudent.size();
  29. }
  30. };

发表评论

表情:
评论列表 (有 0 条评论,67人围观)

还没有评论,来说两句吧...

相关阅读