Weekly Contest 400

日期 2024/06/02

LeetCode 週賽網站變得不穩定，介面跳了兩次。
這次做了前三題題目，最後一題沒想出來，根據討論區的解法，比想像中簡單很多。
該解題達人在 LinkedIn 有創立解題與面試社團，順手就加入該社團。

• Minimum Number of Chairs in a Waiting Room
• Count Days Without Meetings
• Lexicographically Minimum String After Removing Stars
• Find Subarray With Bitwise AND Closest to K

第一題

int minimumChairs(string s) {
    const int n = s.size();
    int ret = 0;
    int cur = 0;
    for(char x: s) {
        cur += x == 'E';
        cur -= x == 'L';
        ret = max(ret, cur);
    }
    return ret;
}

第二題

這題是 Blind 75 中 Interval 題型。

int countDays(int days, vector<vector<int>>& meetings) {
    const int n = meetings.size();
    sort(meetings.begin(), meetings.end());
    /*
    [[5,7],[1,3],[9,10]] --> [1, 3], [5, 7], [9, 10];
    */
    vector<vector<int>> mm;
    mm.push_back(meetings[0]);
    for(int i = 1; i < n; i++) {
        vector<int> &b = mm.back();
        if(b[1] >= meetings[i][0]) {
            b[1] = max(b[1], meetings[i][1]);
        }else{
            mm.push_back(meetings[i]);
        }
    }

    int sum = 0;
    for(auto &x: mm) {
        sum += x[1] - x[0] + 1;
    }
    return days - sum;
}

第三題

剛開始我是想用 stack 保存位址與字元使用，後來改為使用 priority_queue 。自訂結構體 struct foo，保存字元與位址。

1. 遇到 *，就要將目前最小數值的字元從字串移除，複數個相同字元則移除距離最近的字元。因此需要自訂排序，對照 cmp 函式。
2. 將priority_queue 元素全部取出，並以位址從小到大排序，對照 cmp2 函式。
3. 計算結果並輸出。

class Solution {
public:
    struct foo {
        char v;
        int pos;
    };
    using ff = struct foo;
    string clearStars(string s) {
        const int n = s.size();
        // greater, increasing
        auto cmp = [](ff f1, ff f2) {
            if (f1.v == f2.v)
                return f1.pos < f2.pos;
            return f1.v > f2.v;
        };
        priority_queue<ff, vector<ff>, decltype(cmp)> pq;
        for(int i = 0; i < n; i++) {
            if(s[i] != '*') {
                pq.push({.v=s[i], .pos=i});
            }else{
                if(pq.empty()) 
                    continue;
                ff f1 = pq.top();
                pq.pop();
            }
        }
        
        auto cmp2 = [](ff &f1, ff &f2){
            return f1.pos < f2.pos;
        };
        
        vector<ff> med;
        while(!pq.empty()) {
            med.push_back(pq.top());
            pq.pop();
        }
        sort(med.begin(), med.end(), cmp2);
        
        string ret;
        for(ff &f1: med) {
            ret.push_back(f1.v);
        }
        return ret;
    }
};

第四題

第四題題目定義非常簡單，我剛開始的想法為應用位元操作，使得每個子陣列的 AND 結果計算時間複雜度降為

$O(1)$，最終整體時間複雜度為

$O(N^2)$，但實際上沒有這種作法。

第一個版本

這是第一次就能想到的程式碼，但是在 LeetCode 最後幾個測資會超時。

int minimumDifference(vector<int>& nums, int k) {
    const int n = nums.size();
    int ret = INT_MAX;
    for(int i = 0; i < n; i++) {
        int val = nums[i];
        for(int j = i; j < n; j++) {
            val &= nums[j];
            int kv = abs(k - val);
            ret = min(ret, kv);
        }
    }
    return ret;
}

第二個版本

參考討論區解答，使用 Dynamic Programming 剪枝不必要的計算，時間複雜度為

$O(N^2)$
之前學 DP 都是避免重複計算與保留狀態，這裡我是第一次見到可以用來剪枝不必要的運算。

作者表示：

1. 子陣列在 AND 操作過程中會變為非遞增陣列
2. DP Table 定義為以第 j 個元素作為結尾的最大數值(dp[j] stores the maximum bitwise and of a subarray that ends at index j)
3. 剪枝運算
   • dp[j] 最終數值即為 nums[j]
   • 在第 12 行中，作者是用 k - val >= ret || val <= dp[j] 當作 break 條件，因為當 k >= val 且 k - val >= ret，表示接下來的 val 數值只會越小且 |k - val| 會更大

int minimumDifference(vector<int>& nums, int k) {
    const int n = nums.size();
    // dp[j] stores the minimum bitwise and of a subarray that ends at index j
    vector<int> dp(n + 1, 0);
    int ret = INT_MAX;
    for(int i = 0; i < n; i++) {
        int val = nums[i];
        for(int j = i; j < n; j++) {
            val &= nums[j];
            int kv = abs(k - val);
            ret = min(ret, kv);
            // if(k - val >= ret || val <= dp[j])
            if(val <= dp[j])
                break;
            dp[j] = val;
        }
    }
    return ret;
}