每日一题做题记录，参考官方和三叶的题解

题目要求

思路：模拟

• 根据题意可以将所求简化为两种三明治的供需差值，同时发现在这样的规则下，学生的顺序不影响结果；
  • 仅需记录两种三明治的需求数量【学生喜欢】，记为sw0, sw1sw0,\ sw1sw0, sw1；
  • 根据供应栈按顺序消减相应三明治，直至一种需求为000则卡死在当前位置，此时另一种需求剩余数量即为答案。

Java

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] need = new int[2];
        for (int s : students)
            need[s]++;
        for (int s : sandwiches) {
            if (need[s]-- == 0)
                return need[s ^ 1]; // 快速定位另一个
        }
        return 0;
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

C++

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int need[2];
        for (auto s : students)
            need[s]++;
        for (auto s : sandwiches) {
            if (need[s]-- == 0)
                return need[s ^ 1]; // 快速定位另一个
        }
        return 0;
    }
};

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

Rust

impl Solution {
    pub fn count_students(students: Vec<i32>, sandwiches: Vec<i32>) -> i32 {
        let mut need:[i32;2] = [0, 0];
        for s in students {
            need[s as usize] += 1;
        }
        for s in sandwiches {
            if need[s as usize] == 0 {
                return need[(s ^ 1) as usize];
            }
            need[s as usize] -= 1;
        }
        0
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

总结

简单模拟题~

欢迎指正与讨论！