图解LeetCode——1700. 无法吃午餐的弟子数目(难度:简朴)

程序员 2024-9-16 19:35:40 97 0 来自 中国
一、题目

学校的自助午餐提供圆形和方形的三明治,分别用数字 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的时间,则返回两者中最大的谁人值,就是无法吃到午餐的弟子数目。
由于本题逻辑并不复杂,以是就免去画图的步调了。详细实现,请见如下代码实现部分。
四、代码实现
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2024-11-22 17:48, Processed in 0.184302 second(s), 32 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表