【栈】无法吃午餐的学生数量（leetcode1700）

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

## 一、题目 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

## 二、分析 ##

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

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

## 三、题解 ##

C++实现如下：

class Solution { 
    public:
        int countStudents(vector<int>& students, vector<int>& sandwiches) { 
            queue<int> Qstudent;
            stack<int> Ssandwiches;
            for(int num:students) Qstudent.push(num);  //将students重新存入队列里
            reverse(sandwiches.begin(), sandwiches.end());
            for(int num:sandwiches) Ssandwiches.push(num); //将sandwiches重新存入栈中
    
            int cunt = 0;//记录学生连续没有领到三明治的次数
            while(1)
            { 
                if(Qstudent.front()==Ssandwiches.top())
                { 
                    Qstudent.pop();
                    Ssandwiches.pop();
                    cunt = 0;
                }
                else
                { 
                    Qstudent.push(Qstudent.front());
                    Qstudent.pop();
                    cunt += 1;
                }
                // 当cunt超过剩余的学生人数（轮完一周），则说明剩下的学生不再可能领到三明治
                if(cunt>=Qstudent.size() || Qstudent.size()==0)
                    break;
            }
            return Qstudent.size();
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/6c8635edec5f4186bb119d272079a4a4.png