当前位置:网站首页>队列题目:无法吃午餐的学生数量
队列题目:无法吃午餐的学生数量
2022-08-02 06:26:00 【伟大的车尔尼】
题目
标题和出处
标题:无法吃午餐的学生数量
难度
3 级
题目描述
要求
学校的自助午餐提供圆形和方形的三明治,分别用数字 0 \texttt{0} 0 和 1 \texttt{1} 1 表示。所有学生站在一个队列里,每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里,每一轮:
- 如果队列最前面的学生喜欢栈顶的三明治,那么会拿走它并离开队列。
- 否则,这名学生会放弃这个三明治并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组 students \texttt{students} students 和 sandwiches \texttt{sandwiches} sandwiches,其中 sandwiches[i] \texttt{sandwiches[i]} sandwiches[i] 是栈里面第 i \texttt{i} i 个三明治的类型( i = 0 \texttt{i = 0} i = 0 是栈的顶部), students[j] \texttt{students[j]} students[j] 是初始队列里第 j \texttt{j} j 名学生对三明治的喜好( j = 0 \texttt{j = 0} j = 0 是队列的最开始位置)。请你返回无法吃午餐的学生数量。
示例
示例 1:
输入: students = [1,1,0,0], sandwiches = [0,1,0,1] \texttt{students = [1,1,0,0], sandwiches = [0,1,0,1]} students = [1,1,0,0], sandwiches = [0,1,0,1]
输出: 0 \texttt{0} 0
解释:
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [1,0,0,1] \texttt{students = [1,0,0,1]} students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [0,0,1,1] \texttt{students = [0,0,1,1]} students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [0,1,1] \texttt{students = [0,1,1]} students = [0,1,1],三明治栈为 sandwiches = [1,0,1] \texttt{sandwiches = [1,0,1]} sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [1,1,0] \texttt{students = [1,1,0]} students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [1,0] \texttt{students = [1,0]} students = [1,0],三明治栈为 sandwiches = [0,1] \texttt{sandwiches = [0,1]} sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [0,1] \texttt{students = [0,1]} students = [0,1]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [1] \texttt{students = [1]} students = [1],三明治栈为 sandwiches = [1] \texttt{sandwiches = [1]} sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [] \texttt{students = []} students = [],三明治栈为 sandwiches = [] \texttt{sandwiches = []} sandwiches = []。
所以所有学生都有三明治吃。
示例 2:
输入: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] \texttt{students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]} students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
输出: 3 \texttt{3} 3
数据范围
- 1 ≤ students.length, sandwiches.length ≤ 100 \texttt{1} \le \texttt{students.length, sandwiches.length} \le \texttt{100} 1≤students.length, sandwiches.length≤100
- students.length = sandwiches.length \texttt{students.length} = \texttt{sandwiches.length} students.length=sandwiches.length
- sandwiches[i] \texttt{sandwiches[i]} sandwiches[i] 是 0 \texttt{0} 0 或 1 \texttt{1} 1
- students[i] \texttt{students[i]} students[i] 是 0 \texttt{0} 0 或 1 \texttt{1} 1
解法一
思路和算法
可以模拟学生拿三明治的过程。
使用队列存储学生,将数组 students \textit{students} students 中的每个元素依次入队列,然后模拟学生拿三明治的过程,模拟过程中维护队列元素和数组 sandwiches \textit{sandwiches} sandwiches 中遍历到的下标。每次将一个学生出队列,将出队列的学生和数组 sandwiches \textit{sandwiches} sandwiches 的当前下标处的元素比较:
如果两者相等,则当前学生喜欢栈顶的三明治,因此将数组 sandwiches \textit{sandwiches} sandwiches 的下标加 1 1 1,表示学生拿走栈顶的三明治并离开队列;
如果两者不相等,则当前学生不喜欢栈顶的三明治,因此将当前学生重新入队列,表示学生放弃栈顶的三明治并回到队列的尾部。
重复上述过程,直到队列中剩余的学生都拿不到喜欢的三明治。
对于终止条件的判断,基于一点事实:如果队列中剩余的学生都拿不到喜欢的三明治,则没有学生会离开队列。因此,模拟时需要在循环中记录队列大小 size \textit{size} size,每次只将队列中的 size \textit{size} size 个学生出队列并判断他们是否会拿走栈顶的三明治,遍历完 size \textit{size} size 个学生之后,判断队列中的元素个数是否减少,如果元素个数减少则继续模拟,如果元素个数不减少则说明队列中剩余的学生都拿不到喜欢的三明治,达到终止条件,结束模拟。
模拟过程结束后,队列中剩余的学生为无法吃午餐的学生,返回队列中的元素个数即可。
由于三明治的数量与学生的数量相同,因此无法吃午餐的学生数量和剩余的三明治数量相同,当队列中还有剩余的学生时,数组 sandwiches \textit{sandwiches} sandwiches 的下标不会超出数组下标范围。
代码
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
Queue<Integer> queue = new ArrayDeque<Integer>();
int length = students.length;
for (int i = 0; i < length; i++) {
queue.offer(students[i]);
}
int index = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int student = queue.poll();
if (student == sandwiches[index]) {
index++;
} else {
queue.offer(student);
}
}
if (size == queue.size()) {
break;
}
}
return queue.size();
}
}
复杂度分析
时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n n n 是数组 students \textit{students} students 和 sandwiches \textit{sandwiches} sandwiches 的长度。最坏情况下,每次循环都只会使队列元素个数减少 1 1 1 个,因此时间复杂度是 O ( n 2 ) O(n^2) O(n2)。
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 students \textit{students} students 和 sandwiches \textit{sandwiches} sandwiches 的长度。空间复杂度主要取决于队列空间,队列内存储等待拿三明治的学生,队列内的元素个数不会超过 n n n。
解法二
思路和算法
解法一模拟学生拿三明治的过程,因此时间复杂度较高。可以换一个思路,考虑每个三明治是否被学生拿走即可。
由于学生的顺序可以调整,但是三明治的顺序是固定的,因此只需要记录喜欢两种类型的三明治的学生数量,然后判断数组 sandwiches \textit{sandwiches} sandwiches 中的每个三明治是否会被学生拿走。
具体做法是,首先遍历数组 students \textit{students} students,计算喜欢两种类型的三明治的学生数量,然后遍历数组 sandwiches \textit{sandwiches} sandwiches,遍历过程中维护被拿走的三明治的数量 taken \textit{taken} taken,对于每个三明治的类型 type \textit{type} type,进行如下操作:
如果喜欢 type \textit{type} type 类型的三明治的学生数量大于 0 0 0,则当前的三明治一定会被一个学生拿走,因此将喜欢 type \textit{type} type 类型的三明治的学生数量减 1 1 1,将 taken \textit{taken} taken 加 1 1 1;
否则,剩下的学生中没有学生喜欢 type \textit{type} type 类型的三明治,因此当前的三明治不会被任何学生拿走,剩下的学生都无法吃午餐,此时结束遍历。
遍历结束之后,有 taken \textit{taken} taken 个三明治被学生拿走,剩下未被拿走的三明治数量以及无法吃午餐的学生数量为数组长度减 taken \textit{taken} taken。
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int[] counts = new int[2];
int length = students.length;
for (int i = 0; i < length; i++) {
counts[students[i]]++;
}
int taken = 0;
for (int i = 0; i < length; i++) {
int type = sandwiches[i];
if (counts[type] > 0) {
counts[type]--;
taken++;
} else {
break;
}
}
return length - taken;
}
}
复杂度分析
时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 students \textit{students} students 和 sandwiches \textit{sandwiches} sandwiches 的长度。需要遍历数组 students \textit{students} students 和 sandwiches \textit{sandwiches} sandwiches 各一次。
空间复杂度: O ( 1 ) O(1) O(1)。空间复杂度主要取决于记录喜欢两种类型的三明治的学生数量,由于只有两种类型的三明治,因此空间复杂度是 O ( 1 ) O(1) O(1)。
边栏推荐
- PMP新考纲通关秘籍,告别抓瞎
- 每周推荐短视频:为什么产品开发需要数字化?如何做到数字化?
- 技术管理三级跳
- How the Internet of Things is changing the efficiency of city operations
- Py's mlxtend: a detailed guide to the introduction, installation, and usage of the mlxtend library
- Submit code process
- optional
- 实例027:递归输出
- 结构体大小计算--结构体内存对齐
- MySQL classic 50 practice questions and the most detailed analysis of the whole network
猜你喜欢
张驰课堂:六西格玛培训工具——箱线图
(部分不懂,笔记整理未完成)【图论】差分约束
实例027:递归输出
实例031:字母识词
PMP新考纲考试内容介绍
速看!PMP新考纲、PMBOK第七版解读
See the picture to understand | How to choose sales indicators to measure the health of business growth
(Notes are not completed) [Graph Theory] Traversal of graphs
Nodejs installation and global configuration (super detailed)
专家见解|经济低迷期把握创新机会的 3 大方法
随机推荐
Day 4 of HCIP
Revitalize rural circular economy and digital chain to link agricultural "ecological chain"
typescript 'props' is declared but its value is never read solution
MPLS的相关技术
Wuhan 2022 organizing of the high-performance computing added new ecological development of high-performance computing
optional
【论文精读】Geometric Structure Preserving Warp for Natural Image Stitching
2022年7月18日-7月31日(Ue4视频教程和文档,20小时。合计1412小时,剩8588小时)
Servlet
实例029:反向输出
暑期总结(三)
堡垒机、堡垒机的原理
typescript ‘props‘ is declared but its value is never read 解决办法
第06章 索引的数据结构【2.索引及调优篇】【MySQL高级】
MySQL 5.7 installation tutorial (full-step, nanny-level tutorial)
提交代码流程
MySQL Advanced - MVCC (ultra-detailed finishing)
享年94岁,图灵奖得主、计算复杂性理论先驱Juris Hartmanis逝世
abaqus如何快速导入其他cae文件的assembly?
PHP Warning: putenv() has been disabled for security reasons in phar