LeetCode（Queue)1700. Number of Students Unable to Eat Lunch

今天药忘吃喽~ 2023-09-25 19:33 68阅读 0赞

# 1.问题 #

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:

If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.  
Otherwise, they will leave it and go to the queue’s end.  
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches\[i\] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students\[j\] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Example 1:

> Input: students = \[1,1,0,0\], sandwiches = \[0,1,0,1\]  
> Output: 0

Explanation:

>  *  Front student leaves the top sandwich and returns to the end of the line making students = \[1,0,0,1\].
>  *  Front student leaves the top sandwich and returns to the end of the line making students = \[0,0,1,1\].
>  *  Front student takes the top sandwich and leaves the line making students = \[0,1,1\] and sandwiches = \[1,0,1\].
>  *  Front student leaves the top sandwich and returns to the end of the line making students = \[1,1,0\].
>  *  Front student takes the top sandwich and leaves the line making students = \[1,0\] and sandwiches = \[0,1\].
>  *  Front student leaves the top sandwich and returns to the end of the line making students = \[0,1\].
>  *  Front student takes the top sandwich and leaves the line making students = \[1\] and sandwiches = \[1\].
>  *  Front student takes the top sandwich and leaves the line making students = \[\] and sandwiches = \[\].  
>     Hence all students are able to eat.

Example 2:

> Input: students = \[1,1,1,0,0,1\], sandwiches = \[1,0,0,0,1,1\]  
> Output: 3

Constraints:

*  1 <= students.length, sandwiches.length <= 100
 *  students.length == sandwiches.length
 *  sandwiches\[i\] is 0 or 1.
 *  students\[i\] is 0 or 1.

# 2. 解题思路 #

## 方法1： ##

先统计学生中喜欢 0 号三明治和 1 号三明治的数量，然后依次检查每个三明治口味，如果当前口味的三明治数量为 0，那么说明剩余学生中已经没有喜欢这个口味的了，可以返回剩余的学生数量。如果能成功发放所有三明治，剩余学生数量为 0。

## 方法2： ##

1.  使用队列和栈分别存储学生和三明治
2.  将学生和三明治分别添加到队列和栈中
3.  如果当前队首学生喜欢当前栈顶的三明治，则将学生和三明治都出队，并重置计数器
4.  如果当前队首学生不喜欢当前栈顶的三明治，则将该学生放到队列末尾，计数器加1
5.  如果计数器等于队列长度，则说明所有学生都已经按照自己的口味选择了三明治，无法再有学生出队，退出循环
6.  返回队列中剩余学生数量

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int countStudents(int[] students, int[] sandwiches) {
        
            // 统计学生中喜欢 0 号三明治和 1 号三明治的数量
            int[] countZeroAndOne = new int[2];
            for (int i: students) countZeroAndOne[i]++;
    
            // 遍历三明治数组
            for (int i=0;i<sandwiches.length;i++) {
        
                // 如果当前口味的三明治数量为 0，返回剩余的学生数量
                if (--countZeroAndOne[sandwiches[i]] < 0) return sandwiches.length - i;
            }
            // 如果能成功发放所有三明治，剩余学生数量为 0
            return 0;
        }
    }

> 解题思路相同，都是通过数组的0，1个数，根据条件，个数逐次递减

class Solution {
        
        public int countStudents(int[] students, int[] sandwiches) {
        
            // count[0] 和 count[1] 分别表示喜欢 0 号三明治和 1 号三明治的学生数量
            int count[] = {
        0, 0}, n = students.length, k;
            for (int a: students)
                count[a]++;
            
            // 遍历三明治数组，直到遍历完所有三明治或者剩余的学生中没有喜欢这个口味的了
            for (k = 0; k < n && count[sandwiches[k]] > 0; ++k)
                count[sandwiches[k]]--;
            
            // 返回剩余的学生数量
            return n - k;
        }
    }

class Solution {
        
        public int countStudents(int[] students, int[] sandwiches) {
        
            
            // 统计每个口味的三明治和学生的数量
            int[] count = new int[2];
            for (int s : students) count[s]++;
    
            // 遍历三明治数组，如果当前口味的三明治数量为 0，则跳出循环；
            // 否则，将当前口味的三明治数量减 1，表示有一个学生获得了该口味的三明治；
            for (int type : sandwiches) {
        
                if (count[type] == 0) break;
                count[type]--;
            }
            
            // 统计所有剩余学生的数量并返回。
            return IntStream.of(count).sum();
        }
    }

> IntStream.of(count) 是一个 IntStream 类型的流，它包含了整数数组 count 中的所有元素。  
> sum() 方法是 IntStream 类的一个方法，用于计算该流中所有元素的和，并返回结果。所以 IntStream.of(count).sum() 的意思就是将整数数组 count 中所有元素相加并返回结果，这里用于统计所有剩余学生的数量。

class Solution {
        
    	public int countStudents(int[] students, int[] sandwiches) {
        
    	    int zeroCount = 0, oneCount = 0;//1.定义o和1的初始值为0
    	        for(int i : students) {
        //2.遍历循环students，如果是0加1，否则是1加1
    	            if(i == 0) zeroCount ++;
    	            else oneCount ++;
    	        }
    	        for(int s: sandwiches) {
        //3.遍历循环sandwiches，如果是0或者1
    	            if(s == 0) {
        //如果值为0，0的数量如果为0，返回1的数量值，否则0的数量递减
    	                if(zeroCount == 0) return oneCount;
    	                zeroCount --;
    	            }
    	            else {
        //如果值为1，1的数量如果为1，返0的数量值，否则1的数量递减
    	                if(oneCount == 0) return zeroCount;
    	                oneCount--;
    	            }
    	        }
    	        return 0;//否则0和1数量的值为0，返回0
    	}
    }

## 代码2： ##

class Solution {
        
        public int countStudents(int[] students, int[] sandwiches) {
        
            // 使用队列和栈分别存储学生和三明治
            Queue<Integer> studentQueue = new LinkedList<Integer>();
            Stack<Integer> sandwichStack = new Stack<Integer>();
    
            // 将学生和三明治分别添加到队列和栈中
            for (int student : students) {
        
                studentQueue.offer(student);
            }
            for (int i = sandwiches.length - 1; i >= 0; i--) {
        
                sandwichStack.push(sandwiches[i]);
            }
    
            int count = 0; // 记录连续出队次数
            while (!sandwichStack.isEmpty()) {
        
                // 如果当前队首学生喜欢当前栈顶的三明治，则将学生和三明治都出队，并重置计数器
                if (studentQueue.peek() == sandwichStack.peek()) {
        
                    studentQueue.poll();
                    sandwichStack.pop();
                    count = 0;
                } else {
        
                    // 如果当前队首学生不喜欢当前栈顶的三明治，则将该学生放到队列末尾，计数器加1
                    studentQueue.offer(studentQueue.poll());
                    count++;
                    // 如果计数器等于队列长度，则说明所有学生都已经按照自己的口味选择了三明治，无法再有学生出队，退出循环
                    if (count == studentQueue.size()) {
        
                        break;
                    }
                }
            }
            return studentQueue.size(); // 返回队列中剩余学生数量
        }
    }

> 解题思路基本相同，不同的是返回值的，以及while循环的条件不同

class Solution
    
     public int countStudents(int[] students, int[] sandwiches) 
     {
        
    	  Queue<Integer> st = new LinkedList<Integer>();
            Stack<Integer> sa = new Stack<Integer>();
    
            for (int i : students) st.offer(i);
            for (int i = sandwiches.length - 1; i >= 0; i--){
        
                sa.push(sandwiches[i]);
            }
    
            int c = 0;
            while (sa.size()> 0) {
        
                if (st.peek() == sa.peek()){
        
                    st.poll();
                    sa.pop();
                    c = 0;
                } else {
        
                    st.offer(st.remove());
                    c++;
                    if (c == st.size()) return c;
                }
    
            }
            return c;
     }
    }

> 用Arraylist，暴力解法，和以上代码的解题思路是相同的

class Solution {
        
        public int countStudents(int[] students, int[] sandwiches) {
        
            ArrayList<Integer> st = new ArrayList<Integer>(); // 学生队列
            ArrayList<Integer> sa = new ArrayList<Integer>(); // 三明治队列
            for (int i : students) st.add(i); // 将学生队列初始化为输入的学生数组
            for (int i : sandwiches) sa.add(i); // 将三明治队列初始化为输入的三明治数组
            int c = 0; // 用于记录遍历队列的次数
            while (sa.size() > 0) // 当三明治队列不为空时
            {
        
                if (st.get(0) == sa.get(0)) // 如果队首学生想要的三明治与队首三明治一样
                {
        
                    sa.remove(0); // 将该三明治从三明治队列中移除
                    st.remove(0); // 将该学生从学生队列中移除
                    c = 0; // 重置遍历队列的次数
                }
                else
                {
        
                    st.add(st.get(0)); // 将队首学生从学生队列中移到队尾
                    st.remove(0); // 将队首学生从学生队列中移除
                    c++; // 遍历队列的次数+1
                    if (c == st.size()) return c; // 如果遍历次数达到学生队列的长度，说明队列中所有学生都已经遍历了一次，且没有找到想要的三明治，直接返回
                }
            }
            return 0; // 遍历结束，说明所有学生都有了自己想要的三明治，返回0
        }
    }