一、题目
学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
- 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
- 否则，这名学生会 放弃这个三明治 并回到 队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 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[i] 要么是 0 ，要么是 1 。
- students[i] 要么是 0 ，要么是 1 。
三、解题思路
题目描述说了很多，但其实是很好理解的，不会像某些题目描述不清，审题理解需要10多分钟……
其实通过题目描述，我们可以知道这两个数组students和sandwiches各有彼此的特点：
students数组：它就像一把左轮手枪中的子弹一样，只要我们一次次的扣动扳机，每颗子弹我们都有机会发射出去，我们甚至可以将其认为数组中的每个元素，都是平行放在桌子上的，没有什么优先级可言。它是偏动态的。
sandwiches数组：更像靶场的靶子，如果“击中”了，才会更换。而它是有被更换的次序的。它是偏静态的。
那么，题目要求只有students[i]与sandwiches[j]相同的时候，才更换靶子。那么我们其实可以先统计出students数组中“0”的个数（zeroCount）和“1”的个数（oneCount）。然后，我们再将视角切换到sandwiches数组中，从头开始遍历它的元素（即：靶子）。如果是“0”，那么zeroCount减1，否则，oneCount减1。当发现zeroCount或zeroCount为-1的时候，则返回两者中最大的那个值，就是无法吃到午餐的学生数量。
由于本题逻辑并不复杂，所以就免去画图的步骤了。具体实现，请见如下代码实现部分。
四、代码实现
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int oneCount = 0, zeroCount = 0;
for (int student : students) {
if (student == 0) zeroCount++;
else oneCount++;
}
for (int i = 0; i < sandwiches.length; i++) {
if (sandwiches[i] == 0) zeroCount--;
else oneCount--;
if (zeroCount == -1 || oneCount== -1) return Math.max(zeroCount, oneCount);
}
return 0;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论