LeetCode 1700.无法吃午餐的学生数量_学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表示。所有学生站在一

题目描述：无法吃午餐的学生数量

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

我的题解：

真的按照题目思路一遍一遍地遍历三明治，遍历学生…（完全没注意到学生顺序不影响捏）

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) 
    {
        int i = 0;//记录sandwiches走到哪一步
        auto it = students.begin();//学生的编号
        int hungry_num = 0;//初始认为hungry的学生为0
        while(i != sandwiches.size())//sandwich走完 
        {
            if (sandwiches[i] == *it) //栈顶三明治被吃
            {
                hungry_num = 0;
                i++;
                if(it != students.end()-1)
                    it = students.erase(it++);
                else
                {
                    it = students.begin(); 
                    students.pop_back();
                }
            }
            else //第一个学生不吃栈顶三明治  
            {
                if (hungry_num == students.size())//如果hungry的学生达到学生数量,说明已经进入死循环，跳出while，进行输出。
                    break;
                if(it != students.end()-1)
                    it++;//让第二个学生吃
                else
                    it = students.begin();
                hungry_num++;               
            }           
        }
        return hungry_num;
    }
};
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

思路

理解题目不难，就是三明治挨个往后遍历，学生一遍一遍重来，要是学生遍历过一遍之后学生数目还是这么多没减少，说明全部挨饿。

踩坑

开始错了好多地方：

1. while(i != sandwiches.size()) 这边本来写的for循环，后来发现学生+1三明治也+1了。
2. if(it != students.end()-1)这边是最不应该的，我本来没写-1，但是后来运行的时候报溢出错误，猛然醒悟end迭代器是不指向任何元素的，最后一个元素实际上是end()-1
3. it = students.begin();
   students.pop_back();
   这个地方我知道可能会导致迭代器失效所以改过来了，一开始写的是
   students.erase(it);
   it=students.begin();

官方题解

我哭哭，原来这题这么简单，想复杂了捏
思路是这样的：
根据题意，我们可以知道栈顶的三明治能否被拿走取决于队列剩余的学生中是否有喜欢它的，因此学生在队列的相对位置不影响整个过程。
所以根本没必要遍历学生，只要计算喜欢0和喜欢1（大雾）的学生数量即可！又因为学生数量=三明治数量，最终饿肚子的学生数量=三明治数量-得到1的学生数量-得到0的学生数量，剩下的学生只会是一种，要么是三明治栈顶为1但是全是喜欢0的，要么是三明治栈顶为0但是全是喜欢1的。

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int s1 = accumulate(students.begin(), students.end(), 0);
        int s0 = students.size() - s1;
        for (int i = 0; i < sandwiches.size(); i++) {
            if (sandwiches[i] == 0 && s0 > 0) {
                s0--;
            } else if (sandwiches[i] == 1 && s1 > 0) {
                s1--;
            } else {
                break;
            }
        }
        return s0 + s1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18