【每日一题Day1】LC1700.无法吃午餐的学生数量

简介: 给你两个整数数组 students 和 sandwiches ,其中 sandwiches[i] 是栈里面第 i 个三明治的类型(i = 0 是栈的顶部), students[j] 是初始队列里第 j 名学生对三明治的喜好(j = 0 是队列的最开始位置)。请你返回无法吃午餐的学生数量。

LC1700.无法吃午餐的学生数量


学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表示。所有学生站在一个队列里,每个学生要么喜欢圆形的要么喜欢方形的。


餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里,每一轮:


  • 如果队列最前面的学生 喜欢 栈顶的三明治,那么会 拿走它 并离开队列。


  • 否则,这名学生会 放弃这个三明治 并回到队列的尾部。


这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。


给你两个整数数组 students 和 sandwiches ,其中 sandwiches[i] 是栈里面第 i 个三明治的类型(i = 0 是栈的顶部), students[j] 是初始队列里第 j 名学生对三明治的喜好(j = 0 是队列的最开始位置)。请你返回无法吃午餐的学生数量。


希望天天那么简单


队列模拟


使用队列模拟整个取餐过程


class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        Deque<Integer> deque = new LinkedList<>();// 存放学生队列
        int n = students.length;
        for (int i = 0; i < n; i++){
            deque.addLast(students[i]);
        }
        int j = 0;// 三明治的顺序
        while (!deque.isEmpty() && j < n){
            int size = deque.size();
            int i = 0;
            for (; i < size; i++){
                int poll = deque.pollFirst();
                if (poll == sandwiches[j]){
                    j++;
                    break;
                }else{
                    deque.addLast(poll);
                }
            }
            if (i == size){
                break;// 队列里所有学生都不喜欢栈顶的三明治
            }
        }
        return deque.size();
    }
}


  • 复杂度


。时间复杂度:最坏O(n2)


。空间复杂度:O(n)


计数模拟


  • 学生的相对顺序并不影响取餐的过程,因此记录学生队列中喜欢吃圆形三明治s0和方形三明治的数量s1。


  • 然后模拟取餐的过程


。当栈顶元素为0并且s0>0,将s0减1


。当栈顶元素为1并且s1>0,将s1减1


。否则终止过程,返回s0+s1


  • 代码


class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int s1 = Arrays.stream(students).sum();
        int s0 = students.length - s1;
        for (int i = 0; i < sandwiches.length; i++) {
            if (sandwiches[i] == 0 && s0 > 0) {
                s0--;
            } else if (sandwiches[i] == 1 && s1 > 0) {
                s1--;
            } else {
                break;
            }
        }
        return s0 + s1;
    }
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/solutions/1900373/wu-fa-chi-wu-can-de-xue-sheng-shu-liang-fv3f5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


  • 复杂度


。时间复杂度:最坏O(n)


。空间复杂度:O(1)

目录
相关文章
|
6月前
【每日一题Day334】LC2591将钱分给最多的儿童 | 贪心
【每日一题Day334】LC2591将钱分给最多的儿童 | 贪心
46 0
|
6月前
【每日一题Day356】LC2678老人的数目 | 字符串
【每日一题Day356】LC2678老人的数目 | 字符串
49 0
|
6月前
leetcode-1700:无法吃午餐的学生数量
leetcode-1700:无法吃午餐的学生数量
55 0
|
6月前
【每日一题Day180】LC2409统计共同度过的日子数 | 模拟
【每日一题Day180】LC2409统计共同度过的日子数 | 模拟
44 0
|
6月前
【每日一题Day320】LC2651计算列车到站时间 | 数学
【每日一题Day320】LC2651计算列车到站时间 | 数学
45 0
|
6月前
【每日一题Day224】LC2517礼盒的最大甜蜜度 | 二分答案
【每日一题Day224】LC2517礼盒的最大甜蜜度 | 二分答案
32 0
|
算法 Java
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
65 0
|
Python
LeetCode 1700. 无法吃午餐的学生数量
学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表示。
132 0
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球