# Weekly Contest 400
日期 2024/06/02

LeetCode 週賽網站變得不穩定，介面跳了兩次。
這次做了前三題題目，最後一題沒想出來，根據討論區的解法，比想像中簡單很多。
該[解題達人](https://leetcode.com/u/votrubac/)在 LinkedIn 有創立[解題與面試社團](https://www.linkedin.com/groups/13938406/)，順手就加入該社團。

- [Minimum Number of Chairs in a Waiting Room](https://leetcode.com/problems/minimum-number-of-chairs-in-a-waiting-room/)
- [Count Days Without Meetings](https://leetcode.com/problems/count-days-without-meetings/)
- [Lexicographically Minimum String After Removing Stars](https://leetcode.com/problems/lexicographically-minimum-string-after-removing-stars/)
- [Find Subarray With Bitwise AND Closest to K](https://leetcode.com/problems/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;
}

#### 第二個版本
參考[討論區解答](https://leetcode.com/problems/find-subarray-with-bitwise-and-closest-to-k/solutions/5243278/pruning)，使用 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;
}