无法吃午餐的学生数量

标签: 栈 队列 数组 模拟

难度: Easy

学校的自助午餐提供圆形和方形的三明治，分别用数字 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

 

提示：

  • 1 <= students.length, sandwiches.length <= 100
  • students.length == sandwiches.length
  • sandwiches[i] 要么是 0 ，要么是 1 。
  • students[i] 要么是 0 ，要么是 1 。

Submission

运行时间: 27 ms

内存: 16.1 MB

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        ds = Counter(students)
        for i in sandwiches:
            if ds[i] == 0:
                return ds[0] + ds[1] 
            ds[i] -= 1
        return 0

Explain

此题解使用了哈希表（通过Counter类）来记录每种三明治喜好的学生数量。遍历三明治数组，对每个三明治类型，检查是否还有喜欢该类型的学生。如果当前栈顶的三明治类型的学生数已经为零，说明剩下的学生都不喜欢这种类型的三明治，那么函数返回剩余的学生数量。如果还有喜欢该类型的学生，则减少该类型的学生计数。如果所有三明治都被喜欢它们的学生取走，则返回0。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # 使用Counter计算每种三明治喜好的学生数量
        ds = Counter(students)
        # 遍历每个三明治
        for i in sandwiches:
            # 如果没有学生喜欢当前类型的三明治
            if ds[i] == 0:
                # 返回剩余的学生数量
                return ds[0] + ds[1]
            # 否则，减少该类型三明治喜好的学生数量
            ds[i] -= 1
        # 如果所有三明治都被正确取走
        return 0

Explore

使用哈希表(Counter)可以快速跟踪和更新每种三明治喜好的学生数量。这种数据结构使得每次检索和更新学生偏好计数都是常数时间复杂度的操作，从而提高了算法的效率。在处理大量数据时，尤其是学生和三明治数量较多的情况下，这种方法比遍历学生数组来更新喜好计数更高效。

这个条件检查的是当前类型的三明治是否还有学生喜欢。如果`ds[i] == 0`，说明没有学生喜欢这种类型的三明治了。在这种情况下，剩下的学生都喜欢另一种类型的三明治，因为当前类型的三明治已经没有对应喜欢它的学生了。这个检查是为了确定是否还能继续分发当前类型的三明治，以及是否需要直接返回剩余的学生数量。

如果学生队列中的喜好顺序与三明治栈的顺序完全相反，会导致每次尝试取出栈顶的三明治时都找不到喜欢它的学生。因此，每次都需要遍历完所有的学生，直到找到喜欢当前栈顶三明治的学生。在这种极端情况下，算法的效率会降低，因为每次分发三明治都会遇到最坏情况，即没有学生喜欢栈顶的三明治，最后返回的剩余学生数量会是最大的。

剩余的学生数量是通过计算哈希表中所有剩余学生计数的总和得出。在题解中，当发现没有学生喜欢当前三明治类型时（即`ds[i] == 0`），算法会直接返回`ds[0] + ds[1]`的值，这个值表示喜欢0号和1号三明治的学生的剩余总数。这考虑到了所有未被满足的学生，无论他们的喜好如何。