【LeetCode】无法吃午餐的学生数量 Java 题解

作者：Albert

2022-10-21
北京
本文字数：1612 字
阅读完需：约 1 分钟

题目描述

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

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

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

示例 1：
输入：students = [1,1,0,0], sandwiches = [0,1,0,1]输出：0 解释：- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。所以所有学生都有三明治吃。
示例 2：
输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]输出：3

复制代码

思路分析

今天的算法题目是数组类型题目。题目比较长，简单来说，就是学校提供两种规格的三明治，学生只吃自己喜欢的三明治，当遇到不喜欢的三明治的时候，需要重新排队获取三明治，需要返回无法吃午餐的学生数量。
我们首先可以使用朴素解法，直接模拟这个过程。采用双端队列，首先将 students 和 sandwiches 一起放入队列，然后比较 sandwiches 队首是否和 students 队首相同，如果相同，同时出队。如果不同，则调整 students 队列的顺序。在实际操作中，我们使用 Deque 这种数据结构来操作这个过程，Deque 的特性是一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合，使用起来非常方便。
具体实现代码如下，供参考。

通过代码

class Solution {    public int countStudents(int[] students, int[] sandwiches) {        Deque<Integer> studentsStack = new ArrayDeque<>();        Deque<Integer> sandwichesStack = new ArrayDeque<>();        for (int student : students) {            studentsStack.offerLast(student);        }        for (int sandwich : sandwiches) {            sandwichesStack.offerLast(sandwich);        }        int cnt = 0;        while (!studentsStack.isEmpty() && !sandwichesStack.isEmpty()) {            int n = studentsStack.size();            if (sandwichesStack.getFirst().equals(studentsStack.getFirst())) {                sandwichesStack.removeFirst();                studentsStack.removeFirst();                cnt = 0;            } else {                studentsStack.offerLast(studentsStack.removeFirst());                cnt++;            }            if (cnt >= n) {                break;            }        }        return studentsStack.size();    }}