无法吃午餐的学生数量
难度:
标签:
题目描述
代码结果
运行时间: 27 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用 Java Stream API 统计学生喜欢的三明治的类型数量。
* 2. 依次查看三明治栈顶的三明治类型,若有学生喜欢该类型,则移除对应数量。
* 3. 若无学生喜欢,直接返回剩余的学生数量。
*/
import java.util.Arrays;
public class Solution {
public int countStudents(int[] students, int[] sandwiches) {
long count0 = Arrays.stream(students).filter(s -> s == 0).count();
long count1 = students.length - count0;
for (int sandwich : sandwiches) {
if (sandwich == 0) {
if (count0 == 0) return (int) count1;
count0--;
} else {
if (count1 == 0) return (int) count0;
count1--;
}
}
return 0;
}
}
解释
方法:
此题解使用了哈希表(通过Counter类)来记录每种三明治喜好的学生数量。遍历三明治数组,对每个三明治类型,检查是否还有喜欢该类型的学生。如果当前栈顶的三明治类型的学生数已经为零,说明剩下的学生都不喜欢这种类型的三明治,那么函数返回剩余的学生数量。如果还有喜欢该类型的学生,则减少该类型的学生计数。如果所有三明治都被喜欢它们的学生取走,则返回0。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
请问为什么题解中使用哈希表(Counter)来跟踪三明治喜好的学生数量是必要的?
▷🦆
在循环中检查`if ds[i] == 0`时,这个条件具体是为了解决什么问题?
▷🦆
如果队列中的学生顺序和三明治栈的顺序完全相反会怎样影响算法的执行?
▷🦆
在算法描述中,提到了`返回剩余的学生数量`,这里的剩余学生数量是如何计算的?
▷