刷题打卡,第 32 天
题目一、1700. 无法吃午餐的学生数量
题目一、1700. 无法吃午餐的学生数量
原题链接: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 。
解题思路:
从题目中,我们可以知道,三文治的数量与排队学生的数量是相等的,当队伍中的学生遇到喜欢吃的三文治,会取走并离开队伍,离开就代表元素从数组中删除,排队的学生存放在数组中,我们不方便执行删除操作,所以需要遍历学生数组,将元素放到List集合中,可以使用remove()方法进行删除操作。
为了模拟题目中排队的情形,我们同时遍历三文治数组 与 学生集合,会有两种情况:
当遍历到的两个元素相等(学生遇到喜欢吃的三文治),这时候我们将学生元素从集合中删除,List集合使用remove()方法删除元素后,后续元素会向前移动一位,所以学生集合下标无需后移,而三文治数组的下标后移一位。
当遍历到的两个元素不同(学生遇到不爱吃的三文治),那么就向后遍历学生集合,也就是遍历学生集合的下标向后移动一位,继续与当前位置的三文治数组元素进行比较。
因为没有遇到喜欢三文治的学生会回到队尾继续排队,所以我们需要在学生集合遍历到尾部时进行判断,判断也会遇到两种情况:
当这一轮遍历过程中,所有队伍中所有学生都没有遇到喜欢的三文治,即学生集合中没有与当前位置三文治数组元素相等的元素,这时候我们可以停止遍历了。
当这一轮遍历中有学生取到喜欢的三文治离开队伍,那么我们将遍历学生集合的下标归零,不断重复遍历,直到遍历完当轮后,得到第一种情况而停止遍历。
当我们的遍历停止,依旧有两种情况:
因为遍历完三文治数组而停止(三文治被取光);
因为队伍中已经不存在喜欢当前三文治类型的人而停止遍历(三文治数组没有遍历到最后)
但是面对两种情况,我们的操作是相同的,那就是返回无法吃午餐的学生个数,也就是返回剩余的三文治数量:三文治总数减去被遍历过的三文治数量。
因为三文治数量与学生数量一致,我们也可以用学生总数作为被减数,减去被遍历过的三文治数量。
提交代码:
class Solution { public int countStudents(int[] students, int[] sandwiches) { int sandwiches_length = sandwiches.length; //获取三文治的总个数 int sw = 0; //表示三文治数组下标 int st = 0; //表示学生集合下标 boolean flag = false; //设计标记,默认为false,表示没有学生取到喜欢的三文治 List<Integer> list = new ArrayList<>(); //创建List集合 for(int student : students){ //遍历学生数组 list.add(student); //将学生数组元素存进集合中 } while(sw <= sandwiches_length){ //同时便利学生集合与三文治数组 if(st >= list.size()){ //学生集合遍历完一轮后 if(flag){ //当轮遍历中,有学生取到喜欢的三文治 flag = false; //标记恢复默认false st = 0; //学生集合下标归0,遍历重新排队的学生 }else{ //剩下的所有学生都取不到喜欢的三文治 break; //停止遍历 } } if(list.size() != 0){ //判断学生集合是否为空,避免报错 if(list.get(st) == sandwiches[sw]){ //两个遍历到的元素相等 flag = true; //标记设置为true list.remove(st); //学生离开队伍(删除当前学生元素) sw++; //三文治数组下标后移(向后遍历) }else{ //学生没有取到喜欢的三文治 st++; //学生集合下标后移,继续下一次比较 } } } return sandwiches_length-sw; //返回无法吃午餐的学生个数 } }
提交结果:
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞,收藏以及关注是对作者最大的鼓励喔 ~~