LeetCode Biweekly Contest 42

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
573 / 6631	YoungForest	12	0:51:14	0:19:42	0:24:42 1	0:46:14	Debugged it one minute too late. So annoying!

1700. Number of Students Unable to Eat Lunch

Simulate the eating process described in the problem. In fact, because of the termination-condition check, the implementation is not that straightforward.

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        const int n = students.size();
        int ans = 0;
        queue<int> stu;
        for (int i : students) {
            stu.push(i);
        }
        stack<int> sand;
        for (int i = sandwiches.size() - 1; i >= 0; --i) {
            sand.push(sandwiches[i]);
        }
        while (!stu.empty()) {
            int current = stu.size();
            while (!stu.empty()) {
                int s = stu.front();
                stu.pop();
                if (s == sand.top()) {
                    sand.pop();
                    ++ans;
                    break;
                } else {
                    --current;
                    stu.push(s);
                    if (current == 0) {
                        return n - ans;
                    }
                }
            }
        }
        return 0;
    }
};

Time complexity: O(students.size() * sandwiches.size()),
space complexity: O(students.size() + sandwiches.size()).

Actually my implementation made it too complicated. Since we need to traverse students anyway, the students’ order does not really matter. We can count the types students like, then continuously check whether the top of the sandwiches stack can be consumed.

1701. Average Waiting Time

Simulate the cooking process. For each customer, determine whether cooking can start immediately when they arrive.

class Solution {
    using ll = long long;
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        ll wait = 0;
        ll current = 0;
        for (const auto& v : customers) {
            if (current <= v[0]) {
                current = v[0] + v[1];
                wait += v[1];
            } else {
                wait += (current + v[1] - v[0]);
                current += v[1];
            }
        }
        double n = customers.size();
        return wait / n;
    }
};

Time complexity: O(customers.size()),
space complexity: O(1).

1702. Maximum Binary String After Change

Greedy. The idea is in the comments.

class Solution {
    // greedy: change first two op
    // 00 -> 10
    // 01 -> change after substring, 后面可以是0吗？010 -> 001 -> 101, recurse i + 1
    //                             是 1 变 0，找0 向后传导即可。
    // 10 -> do not change, recurse i + 1
    // 11 -> do not change, recurse i + 2
    
    // 时间复杂度： N * 4
    
    // 1 会越变越多，然后往后移
public:
    string maximumBinaryString(string binary) {
        int firstZero = -1;
        auto updateFirstZero = [&]() -> void {
            ++firstZero;
            while (firstZero < binary.size() && binary[firstZero] != '0') {
                ++firstZero;
            }
        };
        updateFirstZero();
        function<void(const int)> recurse = [&](const int i) -> void {
            if (i >= binary.size()) return;
            if (i + 1 == binary.size()) {
                return;
            }
            auto begin = binary.substr(i, 2);
            if (begin == "11") {
                recurse(i + 2);
            } else if (begin == "10") {
                recurse(i + 1);
            } else if (begin == "00") {
                binary[i] = '1';
                recurse(i + 1);
            } else { // "01"
                while (firstZero <= i) {
                    updateFirstZero();
                }
                if (firstZero >= binary.size()) return;
                binary[firstZero] = '1';
                updateFirstZero();
                binary[i] = '1';
                binary[i + 1] = '0';
                binary[i + 2] = '1';
                recurse(i + 1);
            }
        };
        recurse(0);
        return binary;
    }
};

Time complexity: O(binary.size()),
space complexity: O(binary.size()).

In fact, there is also Han Shen’s simpler solution.

1703. Minimum Adjacent Swaps for K Consecutive Ones

Enumerate the center position of the set, and use two pointers to update the left and right boundaries.

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
class Solution {
    // 二分？ 如何判定？N * log N
    // greedy, 向密的地方靠近
    // 把1移到对应位置的花费是中间0的数目
    // 遍历集合地点，然后左右找k个1. N * K
    // 右边取 x 个，左边取 k - x个
    // 贪心， 左边右边谁近取谁
    // 更新集合位置，双指针更新左右边界
public:
    int minMoves(vector<int>& nums, int k) {
        vector<int> ones;
        int zero = 0;
        for (int i : nums) {
            if (i == 1) {
                ones.push_back(zero);
            } else {
                ++zero;
            }
        }
        zero = 0;
        int one = 0;
        int left = 0, right = 0;
        int ans = 0;
        int currentAns = 0;
        // [left, right)
        for (; right < k; ++right) {
            currentAns += ones[right];
        }
        ans = currentAns;
        for (int mid = 0; mid < nums.size(); ++mid) {
            if (nums[mid] == 0) {
                ++zero;
                currentAns -= right - one; // right
                currentAns += one - left; // left;
            } else {
                ++one;
            }
            
            while (right < ones.size() && ones[right] - zero <= zero - ones[left]) {
                currentAns += ones[right] - zero - (zero - ones[left]);
                ++right;
                ++left;
            }
            ans = min(ans, currentAns);
        }
        return ans;
    }
};

Time complexity: O(N),
space complexity: O(N).

During the contest, I spent half an hour debugging two bugs. I missed submission by one minute. Huge loss.