标题链接:https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/
标题形貌:
学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表现。全部学生站在一个队列里,每个学生要么喜好圆形的要么喜好方形的。
餐厅里三明治的数目与学生的数目雷同。全部三明治都放在一个 栈 里,每一轮:
- 假如队列最前面的学生 喜好 栈顶的三明治,那么会 拿走它 并离开队列。
- 否则,这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会不绝连续到队列里全部学生都不喜好栈顶的三明治为止。
给你两个整数数组 students 和 sandwiches ,其中 sandwiches 是栈内里第 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提示:
- 1 <= students.length, sandwiches.length <= 100
- students.length == sandwiches.length
- sandwiches 要么是 0 ,要么是 1 。
- students 要么是 0 ,要么是 1 。
解法:堆栈 + 模拟
使用两个堆栈studentsStack 和sandwichesStack分别来模拟学生队列和三明治队列。当队首元素雷同时,都推出队首元素,开始比力下一个队首元素。否则,让学生队列的队首移动到队尾,继续比力,直到全部元素都匹配不上大概全部元素都已出栈,退出循环,studentsStack 末了剩余的巨细就是无法吃午餐的学生数目。
代码: |