LeetCode 1700《无法吃午餐的学生数量》从队列模拟到频率计数的三种解法全解附 9 种语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文围绕 LeetCode 1700「Number of Students Unable to Eat Lunch」展开完整讲解该题最核心的三种思路队列模拟、循环索引迭代与频率计数并附上 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust 九种语言的完整可运行代码、复杂度分析与常见误区。读完本文你不仅能写出正确解还能理解「学生顺序无关」这一关键洞察从而把 O(n²) 的模拟优化到 O(n) 的计数解法。前置知识在动手写题解前建议先确认自己已掌握以下三个基础知识点对应本仓库文章 articles/number-of-students-unable-to-eat-lunch.md 中列出的 Prerequisites队列Queue数据结构FIFO先进先出结构用于管理需要按顺序处理的元素。本题目中学生在队首检查三明治、不匹配就回到队尾天然适合用队列建模。模拟Simulation严格按题目描述逐步执行流程的能力。本题第一、二种解法都是对取餐过程的忠实模拟。频率计数Frequency Counting用数组或哈希表统计不同值的出现次数。第三种解法正是依赖这一技巧将复杂度降至线性。题目背景可概括为students数组代表排队学生的偏好0表示圆形三明治1表示方形三明治sandwiches数组代表三明治堆栈只能取栈顶。每次学生只能拿走与自己偏好匹配的栈顶三明治否则回到队尾重新排队。当栈顶三明治没有任何剩余学生想要时取餐过程终止问最终有多少学生吃不上饭。解法一队列模拟Queue思路Intuition严格按题目描述模拟取餐过程学生排成队列只有队首学生的偏好与当前栈顶三明治一致时才能取餐否则该学生回到队尾继续排队。当栈顶三明治无法被队列中任何剩余学生取走时过程停止。队列天然建模了「学生不断轮转直到匹配」的行为因此这是最贴合题意、最容易想清楚的解法。算法步骤用学生偏好初始化一个队列。从上到下遍历每个三明治轮转队列中的学生直到找到想要当前三明治的人或已经轮转过全部剩余学生找到匹配学生则将其移出队列并把「吃不上饭的学生数」减 1若完整轮转一圈后仍无人想要当前三明治停止整个过程。返回队列中剩余的学生数量即吃不上饭的人数。多语言实现class Solution: def countStudents(self, students: List[int], sandwiches: List[int]) - int: n len(students) q deque(students) res n for sandwich in sandwiches: cnt 0 while cnt n and q[0] ! sandwich: cur q.popleft() q.append(cur) cnt 1 if q[0] sandwich: q.popleft() res - 1 else: break return respublic class Solution { public int countStudents(int[] students, int[] sandwiches) { int n students.length; QueueInteger q new LinkedList(); for (int student : students) { q.offer(student); } int res n; for (int sandwich : sandwiches) { int cnt 0; while (cnt n q.peek() ! sandwich) { q.offer(q.poll()); cnt; } if (q.peek() sandwich) { q.poll(); res--; } else { break; } } return res; } }class Solution { public: int countStudents(vectorint students, vectorint sandwiches) { int n students.size(); queueint q; for (int student : students) { q.push(student); } int res n; for (int sandwich : sandwiches) { int cnt 0; while (cnt n q.front() ! sandwich) { q.push(q.front()); q.pop(); cnt; } if (q.front() sandwich) { q.pop(); res--; } else { break; } } return res; } };class Solution { /** * param {number[]} students * param {number[]} sandwiches * return {number} */ countStudents(students, sandwiches) { let n students.length; let q new Queue(); for (let student of students) { q.push(student); } let res n; for (let sandwich of sandwiches) { let cnt 0; while (cnt n q.front() ! sandwich) { q.push(q.pop()); cnt; } if (q.front() sandwich) { q.pop(); res--; } else { break; } } return res; } }public class Solution { public int CountStudents(int[] students, int[] sandwiches) { int n students.Length; Queueint q new Queueint(); foreach (int student in students) { q.Enqueue(student); } int res n; foreach (int sandwich in sandwiches) { int cnt 0; while (cnt n q.Peek() ! sandwich) { q.Enqueue(q.Dequeue()); cnt; } if (q.Peek() sandwich) { q.Dequeue(); res--; } else { break; } } return res; } }func countStudents(students []int, sandwiches []int) int { n : len(students) q : make([]int, n) copy(q, students) res : n for _, sandwich : range sandwiches { cnt : 0 for cnt n q[0] ! sandwich { q append(q[1:], q[0]) cnt } if q[0] sandwich { q q[1:] res-- } else { break } } return res }class Solution { fun countStudents(students: IntArray, sandwiches: IntArray): Int { val n students.size val q ArrayDequeInt() for (student in students) { q.add(student) } var res n for (sandwich in sandwiches) { var cnt 0 while (cnt n q.first() ! sandwich) { q.add(q.removeFirst()) cnt } if (q.first() sandwich) { q.removeFirst() res-- } else { break } } return res } }class Solution { func countStudents(_ students: [Int], _ sandwiches: [Int]) - Int { let n students.count var q students var res n for sandwich in sandwiches { var cnt 0 while cnt n q[0] ! sandwich { q.append(q.removeFirst()) cnt 1 } if q[0] sandwich { q.removeFirst() res - 1 } else { break } } return res } }impl Solution { pub fn count_students(students: Veci32, sandwiches: Veci32) - i32 { let n students.len(); let mut q VecDeque::from(students); let mut res n as i32; for sandwich in sandwiches { let mut cnt 0; while cnt q.len() *q.front().unwrap() ! sandwich { let front q.pop_front().unwrap(); q.push_back(front); cnt 1; } if *q.front().unwrap() sandwich { q.pop_front(); res - 1; } else { break; } } res } }复杂度分析时间复杂度O(n²)。外层遍历 n 个三明治内层最坏情况下每处理一个三明治都要轮转全部剩余学生。空间复杂度O(n)。队列需要存储 n 个学生的偏好。仓库源码对照另一种队列模拟写法本仓库的提交实现提供了同思路的变体写法可对照阅读python/1700-number-of-students-unable-to-eat-lunch.py用students.pop(0)/students.append(curr_student)模拟出队/回队并用num_of_students_back_in_line记录连续回队人数当它等于剩余学生数时终止循环cpp/1700-number-of-students-unable-to-eat-lunch.cpp用std::queueint 一个sandwichPos指针curr超过队列长度即判定无学生能匹配当前三明治javascript/1700-number-of-students-unable-to-eat-lunch.js用shift()/push()直接操作数组movement students.length时终止swift/1700-number-of-students-unable-to-eat-lunch.swift手写链表版QueueListNodeenqueue/dequeue并把三明治数组逆序当作栈使用。对比可见无论用语言内置队列还是手写队列核心逻辑都一致——队首不匹配就轮转连续轮转一圈无匹配即终止。解法二循环索引迭代Iteration思路Intuition不用单独的队列而是在原始students数组上用循环下标模拟轮转。学生取走三明治后把其位置标记为已服务用-1占位。这样省去了队列操作的额外开销行为与队列模拟完全一致但空间复杂度降为 O(1)。算法步骤用一个会在students数组上绕圈的索引指针idx。对每个三明治在尚未服务的学生中查找想要当前三明治的人最多检查 n 次找到后把该位置标记为-1已服务并让剩余计数减 1若检查完全部剩余学生仍无匹配停止。返回吃不上饭的学生数量。多语言实现class Solution: def countStudents(self, students: List[int], sandwiches: List[int]) - int: n len(students) idx 0 res n for sandwich in sandwiches: cnt 0 while cnt n and students[idx] ! sandwich: idx 1 idx % n cnt 1 if students[idx] sandwich: students[idx] -1 res - 1 else: break return respublic class Solution { public int countStudents(int[] students, int[] sandwiches) { int n students.length; int idx 0; int res n; for (int sandwich : sandwiches) { int cnt 0; while (cnt n students[idx] ! sandwich) { idx; idx % n; cnt; } if (students[idx] sandwich) { students[idx] -1; res--; } else { break; } } return res; } }class Solution { public: int countStudents(vectorint students, vectorint sandwiches) { int n students.size(); int idx 0; int res n; for (int sandwich : sandwiches) { int cnt 0; while (cnt n students[idx] ! sandwich) { idx; idx % n; cnt; } if (students[idx] sandwich) { students[idx] -1; res--; } else { break; } } return res; } };class Solution { /** * param {number[]} students * param {number[]} sandwiches * return {number} */ countStudents(students, sandwiches) { let n students.length; let idx 0; let res n; for (let sandwich of sandwiches) { let cnt 0; while (cnt n students[idx] ! sandwich) { idx; idx % n; cnt; } if (students[idx] sandwich) { students[idx] -1; res--; } else { break; } } return res; } }public class Solution { public int CountStudents(int[] students, int[] sandwiches) { int n students.Length; int idx 0; int res n; foreach (int sandwich in sandwiches) { int cnt 0; while (cnt n students[idx] ! sandwich) { idx; idx % n; cnt; } if (students[idx] sandwich) { students[idx] -1; res--; } else { break; } } return res; } }func countStudents(students []int, sandwiches []int) int { n : len(students) idx : 0 res : n for _, sandwich : range sandwiches { cnt : 0 for cnt n students[idx] ! sandwich { idx idx % n cnt } if students[idx] sandwich { students[idx] -1 res-- } else { break } } return res }class Solution { fun countStudents(students: IntArray, sandwiches: IntArray): Int { val n students.size var idx 0 var res n for (sandwich in sandwiches) { var cnt 0 while (cnt n students[idx] ! sandwich) { idx idx % n cnt } if (students[idx] sandwich) { students[idx] -1 res-- } else { break } } return res } }class Solution { func countStudents(_ students: [Int], _ sandwiches: [Int]) - Int { var students students let n students.count var idx 0 var res n for sandwich in sandwiches { var cnt 0 while cnt n students[idx] ! sandwich { idx 1 idx % n cnt 1 } if students[idx] sandwich { students[idx] -1 res - 1 } else { break } } return res } }impl Solution { pub fn count_students(mut students: Veci32, sandwiches: Veci32) - i32 { let n students.len(); let mut idx 0; let mut res n as i32; for sandwich in sandwiches { let mut cnt 0; while cnt n students[idx] ! sandwich { idx (idx 1) % n; cnt 1; } if students[idx] sandwich { students[idx] -1; res - 1; } else { break; } } res } }复杂度分析时间复杂度O(n²)。与队列模拟相同最坏情况下每处理一个三明治要绕数组一圈。空间复杂度O(1)。原地标记不需要额外队列Rust 中students需声明为mutSwift 中对传入数组做了值拷贝其余语言均为原地修改。注意该解法会修改传入的students数组。若你的评测环境不允许破坏入参请先复制一份再操作。解法三频率计数Frequency Count思路Intuition关键洞察学生的顺序其实无关紧要。因为学生可以无限次轮转真正起决定作用的只有一件事——当前栈顶三明治是否还有任何学生想要。因此我们只需统计偏好为0和偏好为1的学生各有多少人就能在不模拟队列的情况下快速判断每个三明治能否被取走。这同时也是题目最常见的「最佳解法」。算法步骤统计喜欢每种三明治的学生人数。按顺序处理每个三明治若至少还有一名学生想要当前三明治则对应计数减 1剩余总数减 1若没有任何学生想要它立即停止——因为三明治是栈结构栈顶之下即使有学生想要的三明治也永远无法被取到。返回剩余的学生数量。多语言实现class Solution: def countStudents(self, students: List[int], sandwiches: List[int]) - int: res len(students) cnt Counter(students) for s in sandwiches: if cnt[s] 0: res - 1 cnt[s] - 1 else: break return respublic class Solution { public int countStudents(int[] students, int[] sandwiches) { int n students.length; int res n; int[] cnt new int[2]; for (int i 0; i n; i) { cnt[students[i]]; } for (int i 0; i n; i) { if (cnt[sandwiches[i]] 0) { res--; cnt[sandwiches[i]]--; } else { break; } } return res; } }class Solution { public: int countStudents(vectorint students, vectorint sandwiches) { int res students.size(); vectorint cnt(2); for (int student : students) { cnt[student]; } for (int s : sandwiches) { if (cnt[s] 0) { cnt[s]--; res--; } else { break; } } return res; } };class Solution { /** * param {number[]} students * param {number[]} sandwiches * return {number} */ countStudents(students, sandwiches) { let res students.length; const cnt new Int32Array(2); for (let student of students) { cnt[student]; } for (let s of sandwiches) { if (cnt[s] 0) { cnt[s]--; res--; } else { break; } } return res; } }public class Solution { public int CountStudents(int[] students, int[] sandwiches) { int res students.Length; int[] cnt new int[2]; foreach (int student in students) { cnt[student]; } foreach (int s in sandwiches) { if (cnt[s] 0) { cnt[s]--; res--; } else { break; } } return res; } }func countStudents(students []int, sandwiches []int) int { res : len(students) cnt : make([]int, 2) for _, student : range students { cnt[student] } for _, s : range sandwiches { if cnt[s] 0 { cnt[s]-- res-- } else { break } } return res }class Solution { fun countStudents(students: IntArray, sandwiches: IntArray): Int { var res students.size val cnt IntArray(2) for (student in students) { cnt[student] } for (s in sandwiches) { if (cnt[s] 0) { cnt[s]-- res-- } else { break } } return res } }class Solution { func countStudents(_ students: [Int], _ sandwiches: [Int]) - Int { var res students.count var cnt [0, 0] for student in students { cnt[student] 1 } for s in sandwiches { if cnt[s] 0 { cnt[s] - 1 res - 1 } else { break } } return res } }impl Solution { pub fn count_students(students: Veci32, sandwiches: Veci32) - i32 { let mut res students.len() as i32; let mut cnt [0i32; 2]; for s in students { cnt[s as usize] 1; } for s in sandwiches { if cnt[s as usize] 0 { cnt[s as usize] - 1; res - 1; } else { break; } } res } }复杂度分析时间复杂度O(n)。一次遍历统计频率一次遍历处理三明治全程线性。空间复杂度O(1)。仅需要一个长度为 2 的计数数组Python 中也可用Counter此时空间为 O(1)因为值域只有{0, 1}两种。为什么频率计数是正确的这个解法的正确性可以这样推演假设当前栈顶是0型三明治而喜欢0的学生人数为 0。那么无论剩余学生如何轮转队首永远没有人想要这个三明治取餐过程必然在这里终止res就是最终答案。反过来只要cnt[s] 0就一定能通过轮转让某个想要s的学生来到队首——学生顺序不影响这一结论这正是第三种解法成立的数学基础也是面试官最希望听到的关键洞察。常见误区Common Pitfalls误区一执着于完整模拟而不是计数新手最容易掉进「老老实实模拟整个队列轮转」的陷阱得到 O(n²) 的复杂度。本题最大的关键点在于学生的顺序无关紧要——既然他们可以无限次轮转那么只需要统计每种三明治的偏好人数即可无需关心谁排在第几个。误区二没有认清终止条件过程的终止条件是「栈顶三明治已无任何剩余学生想要」而不是「所有三明治都被处理完」。三明治是栈结构只能取栈顶一旦某个栈顶三明治无人领取它下面的所有三明治即使与剩余学生偏好完全匹配也永远无法被取到。因此当cnt[s] 0时必须立即break而不是继续向后遍历。这是最容易写错、也最影响答案正确性的地方。误区三混淆栈与队列的访问方式students是队列两端操作队首出、队尾进而sandwiches是栈只能从栈顶取。模拟时一定要区分学生对三明治只能取栈顶不能像数组一样任意下标访问——这正是解法三中「栈顶以下的三明治作废」这一结论的来源。三种解法对比与延伸解法核心思想时间复杂度空间复杂度是否修改入参推荐场景队列模拟FIFO 队列逐人轮转O(n²)O(n)否直观理解题意、验证思路循环索引迭代原数组 环形下标 -1标记O(n²)O(1)是面试中节省空间的折中方案频率计数统计偏好人数按栈顶逐层消耗O(n)O(1)否最优解竞赛与面试首选本仓库中该题的实现与本文对应可作为多语言对照与复现参考python/1700-number-of-students-unable-to-eat-lunch.py队列模拟变体cpp/1700-number-of-students-unable-to-eat-lunch.cpp队列模拟 指针版javascript/1700-number-of-students-unable-to-eat-lunch.js数组 shift/push 模拟rust/1700-number-of-students-unable-to-eat-lunch.rsVecDeque/Vec模拟swift/1700-number-of-students-unable-to-eat-lunch.swift手写链表队列 栈从队列到循环索引再到频率计数这道题完整呈现了「模拟 → 空间优化 → 复杂度优化」的递进路径先保证正确再压缩空间最后抓住「顺序无关」的本质把时间降到线性。建议按这个顺序自行推导一遍三种写法并重点理解解法三的终止条件这类「栈顶阻塞导致后续全部作废」的模式在栈相关题目如括号匹配、单调栈中同样常见。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考