1700. 无法吃午餐的学生数量

🟢 🔖 栈 队列 数组 模拟 🔗 力扣open in new window LeetCodeopen in new window

题目

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:

If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue's end.

This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0Explanation:
Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

Example 2:

Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

Constraints:

1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1.
students[i] is 0 or 1.

题目大意

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

解题思路

传统解法可能会模拟学生排队，复杂度较高。此解法通过统计 0 和 1 的数量直接计算结果：

统计总需求：
- 统计 students 中 1 的需求总数，记为 stuCount。
- 统计 sandwiches 中 1 的供应总数，记为 sandCount。
- 计算二者的差，记为 diff = sandCount - stuCount。
判断差异：
- 如果 diff = 0，说明 sandwiches 中 0, 1 的数量与 students 中 0, 1 的需求完全匹配，所有学生可以吃到三明治，返回 0。
- 如果 diff < 0，说明 sandwiches 中 1 的数量不够，同时 0 的数量多了。
- 如果 diff > 0，说明 sandwiches 中 1 的数量多了，同时 0 的数量不够。
返回结果：
- 从后往前遍历 sandwiches，根据 diff 来判断无法吃午餐的学生数量。
- 如果 diff < 0，从后往前遍历 sandwiches，统计到第 |diff| 个 0 时，这之后的所有人都没有午饭吃。
- 如果 diff > 0，从后往前遍历 sandwiches，统计到第 |diff| 个 1 时，这之后的所有人都没有午饭吃。

复杂度分析

时间复杂度：O(n)，需要遍历三明治数组。
空间复杂度：O(1)，只使用常数额外空间。

代码

var countStudents = function (students, sandwiches) {
	const n = sandwiches.length;
	// 统计学生和三明治的需求
	const sandCount = sandwiches.reduce((acc, cur) => acc + cur, 0); // 三明治中 1 的数量
	const stuCount = students.reduce((acc, cur) => acc + cur, 0); // 学生中 1 的需求数量

	const diff = sandCount - stuCount; // 不同种类需求差异

	// 如果需求完全满足
	if (diff == 0) return 0;

	// 统计未满足的学生
	let zeroCount = 0;
	let oneCount = 0;
	for (let i = 1; i <= n; i++) {
		if (sandwiches[n - i]) {
			oneCount++; // 当前为 1 的三明治
		} else {
			zeroCount++; // 当前为 0 的三明治
		}
		if (diff < 0 && zeroCount + diff == 0) return i; // 0 的需求无法满足
		if (diff > 0 && oneCount - diff == 0) return i; // 1 的需求无法满足
	}
};

1700. 无法吃午餐的学生数量

# 1700. 无法吃午餐的学生数量

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

1700. 无法吃午餐的学生数量

题目

题目大意

解题思路

复杂度分析

代码

相关题目