1700. 無法吃午餐的學生數量

思路

按照題目模擬，用變數cnt紀錄當前不滿足的人數，
如果不滿足的人數等於隊列長度，表示所有人都不滿足，返回結果。

除了模擬之外，也可以單純的計數，只要學生當中有想要吃圓形的三明治，
那麼隊伍總有一天會輪到想吃的那一個人，因此隊列的順序並不重要，
只要計算目前想吃圓形和方形三明治的學生有多少人就好。

程式碼

1. 隊列

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        // 學生隊列
        queue<int> q;
        for(int &stu:students) {
            q.push(stu);
        }
        int index = 0;
        int cnt = 0;
        while(!q.empty()) {
            // 若相同, 兩者相消
            if(q.front() == sandwiches[index]) {
                q.pop();
                ++index;
                cnt = 0; // 重置不滿足的人數
            }
            else {
                // 不相同, 學生移動到後面
                q.push(q.front());
                q.pop();
                ++cnt; // 計算不滿足的人數
            }
            if(cnt == q.size()) break; // 所有人都不滿足
        }
        return sandwiches.size() - index;
    }
};

2. 計數

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int cnt[2]{};
        for(auto stu : students) cnt[stu]++; // 記錄學生想要的三明治。
        for(int i = 0; i < sandwiches.size(); ++i) {
            if(cnt[sandwiches[i]] == 0) return sandwiches.size() - i; // 沒有學生想要吃這種三明治，隊伍陷入死循環
            cnt[sandwiches[i]]--; // 正常解決學生需求
        }
        return 0; // 迴圈正常結束，學生需求全部被滿足

    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：方法一 $O(n)$，方法二 $O(1)$