forked from qscool1987/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
lc_1700.cpp
45 lines (42 loc) · 1.19 KB
/
lc_1700.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
/*
思路:采用队列模拟,当队列top和sandwiches[i]相等时移动i
复杂度O(N^2)
特别注意退出条件,当队列遍历一遍后都没有和sandwiches[i]相等的值则退出
*/
class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
queue<int> que;
for(auto x : students) que.push(x);
for(int i = 0; i < sandwiches.size(); ++i) {
int sz = que.size(); // 用来控制队列刚好遍历一遍
while(sz > 0 && que.front() != sandwiches[i]) {
que.push(que.front());
que.pop();
--sz;
}
if (sz <= 0) return que.size();
que.pop();
}
return 0;
}
};
int main(int argc, const char * argv[]) {
vector<int> students = {1,1,1,0,0,1};
vector<int> sandwiches = {1,0,0,0,1,1};
Solution so;
cout << so.countStudents(students, sandwiches) << endl;
return 0;
}