一、题目
学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表现。全部弟子站在一个队列里,每个弟子要么喜好圆形的要么喜好方形的。餐厅里三明治的数目与弟子的数目类似。全部三明治都放在一个 栈 里,每一轮:
- 假如队列最前面的弟子 喜好 栈顶的三明治,那么会 拿走它 并脱离队列。
- 否则,这名弟子会 放弃这个三明治 并回到 队列的尾部。
这个过程会不停连续到队列里全部弟子都不喜好栈顶的三明治为止。
给你两个整数数组 students 和 sandwiches ,此中 sandwiches 是栈里面第 i 个三明治的范例(i = 0 是栈的顶部), students[j] 是初始队列里第 j 名弟子对三明治的喜好(j = 0 是队列的最开始位置)。请你返回无法吃午餐的弟子数目。
二、示例
2.1> 示例 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.2> 示例 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 。
三、解题思绪
题目形貌说了很多,但其实是很好理解的,不会像某些题目形貌不清,审题理解必要10多分钟……
其实通过题目形貌,我们可以知道这两个数组students和sandwiches各有彼此的特点:
students数组:它就像一把左轮手枪中的子弹一样,只要我们一次次的扣动扳机,每颗子弹我们都有机遇发射出去,我们以致可以将其以为数组中的每个元素,都是平行放在桌子上的,没有什么优先级可言。它是偏动态的。
sandwiches数组:更像靶场的靶子,假如“击中”了,才会更换。而它是有被更换的序次的。它是偏静态的。
那么,题目要求只有students与sandwiches[j]类似的时间,才更换靶子。那么我们其实可以先统计出students数组中“0”的个数(zeroCount)和“1”的个数(oneCount)。然后,我们再将视角切换到sandwiches数组中,重新开始遍历它的元素(即:靶子)。假如是“0”,那么zeroCount减1,否则,oneCount减1。当发现zeroCount或zeroCount为-1的时间,则返回两者中最大的谁人值,就是无法吃到午餐的弟子数目。
由于本题逻辑并不复杂,以是就免去画图的步调了。详细实现,请见如下代码实现部分。
四、代码实现 |