leetcode
leetcode 1501 ~ 1550
无法吃午餐的学生数量

无法吃午餐的学生数量

难度:

标签:

题目描述

代码结果

运行时间: 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)来跟踪三明治喜好的学生数量是必要的?
使用哈希表(Counter)可以快速跟踪和更新每种三明治喜好的学生数量。这种数据结构使得每次检索和更新学生偏好计数都是常数时间复杂度的操作,从而提高了算法的效率。在处理大量数据时,尤其是学生和三明治数量较多的情况下,这种方法比遍历学生数组来更新喜好计数更高效。
🦆
在循环中检查`if ds[i] == 0`时,这个条件具体是为了解决什么问题?
这个条件检查的是当前类型的三明治是否还有学生喜欢。如果`ds[i] == 0`,说明没有学生喜欢这种类型的三明治了。在这种情况下,剩下的学生都喜欢另一种类型的三明治,因为当前类型的三明治已经没有对应喜欢它的学生了。这个检查是为了确定是否还能继续分发当前类型的三明治,以及是否需要直接返回剩余的学生数量。
🦆
如果队列中的学生顺序和三明治栈的顺序完全相反会怎样影响算法的执行?
如果学生队列中的喜好顺序与三明治栈的顺序完全相反,会导致每次尝试取出栈顶的三明治时都找不到喜欢它的学生。因此,每次都需要遍历完所有的学生,直到找到喜欢当前栈顶三明治的学生。在这种极端情况下,算法的效率会降低,因为每次分发三明治都会遇到最坏情况,即没有学生喜欢栈顶的三明治,最后返回的剩余学生数量会是最大的。
🦆
在算法描述中,提到了`返回剩余的学生数量`,这里的剩余学生数量是如何计算的?
剩余的学生数量是通过计算哈希表中所有剩余学生计数的总和得出。在题解中,当发现没有学生喜欢当前三明治类型时(即`ds[i] == 0`),算法会直接返回`ds[0] + ds[1]`的值,这个值表示喜欢0号和1号三明治的学生的剩余总数。这考虑到了所有未被满足的学生,无论他们的喜好如何。

相关问题