无法吃午餐的学生数量 图解题解
这道题到底在问什么
- 输入
- students=[1,1,0,0], sandwiches=[0,1,0,1]
- 输出
- 0
- 输入
- students=[1,1,1,0,0,1], sandwiches=[1,0,0,0,1,1]
- 输出
- 3
- 输入
- students=[0], sandwiches=[0]
- 输出
- 0
最优解：一步一步想明白
- 3记牢一句:学生在队里怎么转都不改各类人的总数,真正决定谁吃不上的是三明治栈的顺序。数清两类人、按栈顶往下发,发到某类没人要就卡住,剩几个就是答案。
- 4先看队伍。从队首到队尾是 [方1, 方2, 方3, 圆4, 圆5, 方6],方表示爱吃方形、圆表示爱吃圆形,编号只是给每个人贴个名牌,方便等会看清谁转到了后面。队首是方1,他排第一个,等会第一轮先轮到他。
- 5再看下面这行三明治栈的说明。从栈顶到栈底依次是方、圆、圆、圆、方、方,栈顶用方括号框出来的就是当前要发的那个。规则是栈顶先发,队首学生爱吃就拿走、栈顶往下走一个;不爱吃就回队尾。开始一轮轮发。
- 6第 1 轮,先看队首的 方1,他爱吃方形。现在栈顶是方形。正好对上了,他爱吃的就是栈顶这个,下一帧他就能拿走离队。
- 7方1 拿走了栈顶这个方形三明治,开开心心离开队伍。栈顶往下走一个,已经吃到饭的人变成 1 个。现在队首换成了 方2,连续放弃的计数也清零,重新开始数。
- 8第 2 轮,先看队首的 方2,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
- 9方2 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 1,队伍长度是 5。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
- 10第 3 轮,先看队首的 方3,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
- 11方3 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 2,队伍长度是 5。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
- 12第 4 轮,先看队首的 圆4,他爱吃圆形。现在栈顶是圆形。正好对上了,他爱吃的就是栈顶这个,下一帧他就能拿走离队。
- 13圆4 拿走了栈顶这个圆形三明治,开开心心离开队伍。栈顶往下走一个,已经吃到饭的人变成 2 个。现在队首换成了 圆5,连续放弃的计数也清零,重新开始数。
- 14第 5 轮,先看队首的 圆5,他爱吃圆形。现在栈顶是圆形。正好对上了,他爱吃的就是栈顶这个,下一帧他就能拿走离队。
- 15圆5 拿走了栈顶这个圆形三明治,开开心心离开队伍。栈顶往下走一个,已经吃到饭的人变成 3 个。现在队首换成了 方6,连续放弃的计数也清零,重新开始数。
- 16第 6 轮,先看队首的 方6,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
- 17方6 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 1,队伍长度是 3。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
- 18第 7 轮,先看队首的 方2,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
- 19方2 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 2,队伍长度是 3。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
- 20第 8 轮,先看队首的 方3,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
- 21方3 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 3,队伍长度是 3。这两个数相等了,意味着这一圈里每个人都对栈顶的圆形摇了头,谁都不会去拿,再转下去也是一样,过程到此必须停下。
- 22停下来时队里还剩 [方6, 方2, 方3] 这 3 个人,他们清一色都只爱吃方形,可栈顶偏偏是圆形,谁来当队首都换不动它。这 3 个人就是无法吃到午餐的学生,答案就是 3。
- 23换个更省事的角度回看。开局数一下,爱吃圆形的有 2 个、爱吃方形的有 4 个。三明治栈从顶往下是方圆圆圆方方,顺着发:第一个方先被一个爱方的拿走,接着连发三个圆,正好把 2 个爱圆的发完后还多出一个圆没人要,这时就卡住了,队里剩下的全是爱方的,还有 3 个。和轮转模拟数出来的完全一致。
⚠️ 容易写错的地方
✗ 错：老老实实模拟轮转,担心队伍要转很多圈、会超时
✓ 对：看清学生轮转不改各类人数,改成数两类人按栈顶顺序发
三明治是固定顺序从栈顶往下发的,谁先被发完只由栈顶顺序决定。把轮转换成计数,时间从最坏 O(n²) 降到 O(n),代码也短得多
✗ 错：判停条件写成「队列空了才停」
✓ 对：一整圈学生都不爱吃栈顶时就得停,这时队列往往还没空
只要当前栈顶这种三明治没人爱吃,后面的人再怎么转也都会跳过它,队列会卡在原地不再缩短。计数法里就是「cnt[v] 已经为 0」这一刻直接返回剩下的人
✗ 错：搞反 0 和 1,或返回时取错了类别
✓ 对：0 是圆形、1 是方形;卡住时返回的是另一种人,用 cnt[v 异或 1]
卡住是因为爱吃栈顶这种 v 的人已为 0,真正吃不上的是剩下爱吃另一种的人。异或 1 正好把 v 翻到另一种,别直接返回 cnt[v],那个已经是 0 了
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
cnt = Counter(students)
for v in sandwiches:
if cnt[v] == 0:
return cnt[v ^ 1]
cnt[v] -= 1
return 0C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int cnt[2] = {0};
for (int& v : students) ++cnt[v];
for (int& v : sandwiches) {
if (cnt[v]-- == 0) {
return cnt[v ^ 1];
}
}
return 0;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int[] cnt = new int[2];
for (int v : students) {
++cnt[v];
}
for (int v : sandwiches) {
if (cnt[v]-- == 0) {
return cnt[v ^ 1];
}
}
return 0;
}
}复杂度
时间
O(n)
参考代码先扫一遍 students 数清两类人,再顺着 sandwiches 从栈顶往下走,各是一趟线性遍历,每步常数操作,合起来是 O(n)。动画里那种真去轮转队伍的笨办法最坏要 O(n²),计数法把它压成了线性
空间
O(1)
按峰值算额外空间:只用了一个长度固定为 2 的计数器 cnt,不随 n 变大,所以是常数。不需要额外开队列或栈,题目给的两个数组是输入、不计入额外开销
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 无法吃午餐的学生数量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么可以不真的模拟轮转,直接计数?+
因为三明治栈是固定顺序、从栈顶一个个往下发,谁先被发到完全由栈顶顺序决定。学生在队里前前后后地转,只是改变了谁当下是队首,并不改变爱吃两种三明治的人各有多少。所以你只要数清两类人,再顺着栈顶往下发,模拟出来的结果和真转队伍一模一样,却把最坏 O(n²) 的轮转压成了 O(n)。
停止的判定到底是什么?为什么不是队列空?+
停止条件是某一刻队里所有人都不爱吃当前栈顶。这等价于「爱吃栈顶这种三明治的人已经为 0」。一旦如此,后面的人轮流当队首也都会跳过它,队列卡在原地不再缩短,所以不能等队列空。计数写法里就是发到某个三明治类型 v 时发现 cnt[v] 已是 0,这时直接返回剩下另一种人的数量。
返回值为什么是 cnt[v 异或 1] 而不是 cnt[v]?+
卡住的原因正是爱吃栈顶这种 v 的人已经一个不剩,cnt[v] 此刻就是 0,返回它毫无意义。真正吃不上饭的,是队里剩下的那批爱吃另一种的人。异或 1 这个小技巧把 0 翻成 1、1 翻成 0,正好取到另一种的人数,一行就拿到了答案。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 无法吃午餐的学生数量 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。