Leetcode1700. 无法吃午餐的学生数量[C++题解]：模拟题简单，用queue_无法吃午餐的学生数量 完整c++代码

题目分析

题意重述：排队领食物，食物2种属性；学生有唯一偏好。如果学生看到食物队头是自己喜欢吃的，拿走；如果学生看到食物队头不是自己喜欢吃的，掉头回到自己队伍中继续排队。

问是否学生都能拿到食物，不能的话返回几个学生不能拿到食物。

思路：采用queue模拟学生和三明治， 模拟学生拿三明治的过程。采用一个标志t，看看学生循环了走了多少次。

时间复杂度分析： 最好情况是遍历一下学生队列，m个学生看到食物队头都不喜欢，整个过程结束；否则，肯定有一个学生拿走第一个食物；然后再次遍历学生队列，对新的食物队头进行观察，以此类推…，最坏情况是每循环m次，干掉1个食物，总共n个食物，所以时间复杂度$O(m\times n)$.这里 m和n都是最大100，所以直接枚举10000次即可肯定可以过。

ac代码

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        queue<int> q,s;
        for(auto c:students) q.push(c);
        for(auto c:sandwiches) s.push(c);
        //暴力枚举10000次即可
        for(int i=0;i<10000 && q.size() && s.size();i++){
            if(q.front()==s.front()){
                q.pop(),s.pop();
            }else{
                int t=q.front();
                q.pop();
                q.push(t);
            }
        }

        return q.size();
    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

ac代码
下面退出条件：循环了队列长度 的5倍次，结果也过 了。

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        queue<int> q,s;
        for(auto c:students) q.push(c);
        for(auto c:sandwiches) s.push(c);
        int t=5*q.size(); //用于退出循环
        while(q.size()){ //学生队列不空
            if(q.front()==s.front()){
                q.pop(),s.pop(); 
            }else{
                int t=q.front();
                q.pop();
                q.push(t);
            }
            t--;
            if(t==0) break;
        }

        return q.size();
    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

题目链接

Leetcode1700. 无法吃午餐的学生数量

补充 Queue的操作

queue队列：先进先出。

queue四个核心接口

push(): 将一个元素放入queue内
front(): 返回queue队头元素
back():返回 queue队尾元素
pop() 删除队头
1
2
3
4