『LeetCode』1700 无法吃午餐的学生数量

题目

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

题解

【无法吃午餐的学生数量】简单模拟&计数

模拟

最简单的方法是将学生放到队列中去，然后模拟整个过程即可

注意控制循环次数避免死循环

# Code language: Python
class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        n = len(students)
        st = deque(range(n))
        for i, s in enumerate(sandwiches):
            for j in range(i, n):
                if students[st[0]] == s:
                    break
                st.rotate(-1)
            if students[st[0]] != s:
                return n - i
            st.popleft()
        return 0

// Code language: Java
class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int n = students.length;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) st.addLast(i);
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n && students[st.peekFirst()] != sandwiches[i]; ++j) st.addLast(st.pollFirst());
            if (students[st.peekFirst()] != sandwiches[i]) {
                return n - i;
            }
            st.pollFirst();
        }
        return 0;
    }
}

// Code language: C++
class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int n = students.size();
        deque<int> st;
        for (int i = 0; i < n; ++i) st.emplace_back(i);
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n && students[st.front()] != sandwiches[i]; ++j) {
                st.emplace_back(st.front()); st.pop_front();
            }
            if (students[st.front()] != sandwiches[i]) {
                return n - i;
            }
            st.pop_front();
        }
        return 0;
    }
};

时间复杂度: \(O(n^2)\), 我能想到的最坏情况是三明治 \([0, 1, 0, 1, ...]\), 然后学生 \(01\) 一样多 \([1, 1, ..., 0, 0, ...]\), 这样每次都要 \(O(n)\), 总共 \(n\) 次
空间复杂度: \(O(n)\)

计数

其实没必要具体模拟，因为只有三明治有人要那么肯定能拿到，所有统计学生中三明治的需求量然后再分配，如果某个三明治没人要那么剩下的人就要饿肚子了。

# Code language: Python
class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        cnt = [students.count(0), students.count(1)]
        for c in sandwiches:
            cnt[c] -= 1
            if cnt[0] < 0 or cnt[1] < 0:
                return sum(cnt) + 1
        return 0

// Code language: Java
class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] cnt = new int[2];
        for (int s: students) cnt[s]++;
        for (int s: sandwiches) {
            cnt[s]--;
            if (cnt[0] < 0 || cnt[1] < 0) return cnt[0] + cnt[1] + 1;
        }
        return 0;
    }
}

// Code language: C++
class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int cnt[]{0, 0};
        for (int s: students) cnt[s]++;
        for (int s: sandwiches) {
            cnt[s]--;
            if (cnt[0] < 0 || cnt[1] < 0) return cnt[0] + cnt[1] + 1;
        }
        return 0;
    }
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1700 无法吃午餐的学生数量

题目

标签

题解

模拟

计数