【Day32】LeetCode刷刷刷。[1700. 无法吃午餐的学生数量 ]

在这里插入图片描述

刷题打卡，第 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✔刷题专栏✔

在这里插入图片描述