跳到主要内容

第 42 场双周赛

Problem A - 无法吃午餐的学生数量​

预先统计喜欢每种三明治的学生人数，并用栈模拟三明治堆。需要注意的是，不需要对学生的队列进行模拟，因为每次一定会找到一个喜欢当前栈顶三明治的学生，所以直接扣减人数即可。如果当前栈顶的三明治对应的学生人数已经为00，则可以提前终止。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
参考代码（C++）
class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        stack<int> st;
        for (int i = (int)sandwiches.size() - 1; i >= 0; --i)
            st.push(sandwiches[i]);
        vector<int> t(2);
        for (int student : students)
            t[student]++;
        while (!st.empty() && t[st.top()]) {
            t[st.top()]--;
            st.pop();
        }
        return st.size();
    }
};

Problem B - 平均等待时间​

因为顾客到达时间是有序的，所以直接模拟即可。记录厨师完成上一道菜的时间，与当前顾客的到达时间比较，就可以得到厨师开始给当前顾客做菜的时间，从而计算出厨师做完这道菜的时间和顾客的等待时间。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(1)\mathcal{O}(1)
参考代码（Python 3）
class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        n = len(customers)
        cook = 0
        wait = 0
        for arrival, duration in customers:
            if arrival >= cook:
                wait += duration
            else:
                wait += cook + duration - arrival
            cook = max(cook, arrival) + duration
        return wait / n

Problem C - 修改后的最大二进制字符串​

借助10->01这一操作，我们可以将所有的1移到字符串末尾；借助00->10这一操作，我们可以将所有的000...000串变为111...110。在这一观察的基础上，容易想到，要得到最大的二进制字符串，我们应该首先把所有不在开头的1移到末尾，使得字符串变为11...1100...0011...11的形式，然后再用第二种操作把中间部分变为11...10。在这一操作顺序下，我们最终得到的字符串中最多包含一个0（考虑初始全为1的特殊情况），并且这个0的位置是尽可能靠后的，因此，得到的字符串就是我们要求的答案。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)
  • 空间复杂度O(∣S∣)\mathcal{O}(|S|)
参考代码（C++）
class Solution {
public:
    string maximumBinaryString(string binary) {
        int n = binary.size();
        int front = 0;
        while (binary[front] == '1' && front < n)
            front++;
        if (front == n)
            return binary;
        int rest = 0;
        for (int i = front; i < n; ++i)
            if (binary[i] == '1')
                rest++;
        string ans(n - rest - 1, '1');
        if (front != n)
            ans.push_back('0');
        ans += string(rest, '1');
        return ans;
    }
};

Problem D - 得到连续 K 个 1 的最少相邻交换次数​

如果之前做过数轴上KK个人碰面的题目，做这道题会相对容易一些。

我们知道，对于KK个人碰面的问题，我们应当将集合的位置选在中位数处，这样可以使得所有人移动的总路程最短。但本题中有一点不同，也即，KK个人并不是集合到同一个位置，而是集合在t,t+1,t+2,…,t+K−1t,t+1,t+2,\dots,t+K-1处。这种情况下，应当如何修改我们的算法呢？

事实上，我们只需要将每个人的原始坐标改为Xi−iX_i-i，就可以将这一问题转化为原来的问题。对应到本题中，我们首先找出所有的1，然后得到它们的等效坐标Xi−iX_i-i（其中ii表示这是第ii个1），接下来，我们用滑动窗口的方法，求出每一段长度为KK的窗口内的“人”在中位数处集合的总移动距离，取其最小值即为答案。

对等效坐标的简单说明​

为什么我们使用了等效坐标之后就可以将问题转化为集合到同一点的问题呢？考虑KK个人的情形。假设第一个人移动到的目标位置是tt，那么第二个人移动到的目标位置就应该是t+1t+1。现在我们假设第二个人的目标位置也是tt，这样就等于是左移了一个单位，为了保证移动的距离相等，我们需要把第二个人的初始位置也左移一个单位，这样就变成了X1−1X_1-1。依此类推，我们就可以得到所有人的等效坐标。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(N)\mathcal{O}(N)
参考代码（C++）
typedef long long ll;

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<ll> one;
        for (int i = 0; i < nums.size(); ++i)
            if (nums[i] == 1)
                one.emplace_back(i - (int)one.size());
        vector<ll> pre{0};
        for (int i : one)
            pre.emplace_back(pre.back() + i);
        ll ans = 1e10;
        for (int l = 1; l + k - 1 <= one.size(); ++l) {
            int r = l + k - 1;
            int mid = (l + r) >> 1;
            ll left = one[mid - 1] * (mid - l) - pre[mid - 1] + pre[l - 1];
            ll right = pre[r] - pre[mid] - one[mid - 1] * (r - mid);
            ans = min(ans, left + right);
        }
        return ans;
    }
};