LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量

英文原文如下

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 i^{​​​​​​th} sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j^{​​​​​​th} student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

中文翻譯

學校的餐廳在午餐休息時間提供圓形以及方形的三明治，分別用數字 0 以及 1 來表示。所有學生排在一個隊列上，每一位學生都有自己心儀的三明治類型。

餐廳的三明治與學生的數量相同，三明治被擺放為一個堆疊，而每一步如下:

• 要是隊列最前面的學生尬意(喜歡)堆疊最上面的三明治，他/她會取走這個三明治並離開這個隊列。
• 不喜歡的話，他/她不會拿走這個三明治然後走到隊列的最後面繼續排隊。

整個動作會持續到隊列中的所有人都不想要取走最上面的三明治，因此他們都吃不到。

給予你兩個整數陣列 students 跟 sandwiches，sandwiches[i] 是堆疊中的第 i 個三明治類別( i = 0 代表堆疊的最上面 )， students[j] 則是代表初始學生隊列中第 j 個學生偏好的三明治類型 ( j = 0 表示的是隊列中的第一位)。回傳吃不到午餐的學生數量。

範例及題目限制

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.

解題思路

這一題當中，我們可以用 Queue 來解決

在題目中的 Queue 表示的是隊伍、隊列，而我們要使用的則是資料結構中的 Queue，可以被翻作隊列或是我喜歡的「佇列」，擁有著FIFO (First In, First Out 先進先出)的特性。

我們用這個來模擬整個隊伍目前的狀況，至於為什麼不用 Array 或是 List呢，肯定是因為很麻煩，不論是要移除掉第一個人，或是移到最後面都是件苦工。

C# 解決方案

方案1

public class Solution {
    public int CountStudents(int[] students, int[] sandwiches) {
        Queue<int> queue = new Queue<int>(students);
        int tmp = 0;

        foreach(var sandwich in sandwiches){
            while (queue.Count>0){
                var student = queue.Dequeue(); //移出佇列中的第一個元素
                if(sandwich==student){
                    tmp=0;
                    break;
                }
                else{
                    if(tmp==queue.Count){
                        return queue.Count+1;
                    }
                    tmp+=1;
                    queue.Enqueue(student); //插入佇列(最後)
                }
            }
        }

        return 0;
    }
}

最外層的 foreach 模擬了三明治堆疊的場合，sandwich 表示目前是哪一個三明治

下一步，我們會依次從佇列最前方來進行判斷，取出來與目前的三明治類型來比較

要是你喜歡，那就拿走他，要是不喜歡，那就去最後面繼續排隊吧

但要注意的是，我們使用了一個變數 tmp 來計算當前的三明治有多少人不要，當佇列當前人數每一個人都問過的時候，我們就要回傳當前佇列的人數(這裡的 queue.Count+1 則是因為前面有一個人先被移出來了，但他也不要故要加回去回傳)

結論

沒學好資料結構的我，看著這些專有名詞總是頭有點痛~

話說那些學生也太誇張了!! 居然因為形狀就不吃午餐了嗎?

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Number of Students Unable to Eat Lunch – LeetCode

隨機掉落的LeetCode文章