LeetCode周賽309，米哈遊贊助的比賽居然不收簡歷……

語言: CN / TW / HK
時間 2022-10-10 16:15:37

大家好，我是梁唐。

LeetCode系列原本是週一更新的，但由於昨天恰了個飯，因此推遲一天。

LeetCode周賽309由大名鼎鼎的米哈遊贊助，米哈遊也是近期唯一一個不提供簡歷直通內推機會的贊助商……

這一場的難度比之前略大一些，很多同學在評論區反應心態崩了……

很遺憾這一場比賽我沒有參加（剛好收到密接簡訊聯絡社群去了……），我是賽後補的。但即便是在賽後比較輕鬆的狀態下，依然做得不是很順利，也側面體現這一場的難度。

好了，我們閒言少敘，來看題吧。

檢查相同字母間的距離

給你一個下標從 0 開始的字串 s ，該字串僅由小寫英文字母組成，s 中的每個字母都 恰好 出現 兩次 。另給你一個下標從 0 開始、長度為 26 的的整數陣列 distance 。

字母表中的每個字母按從 0 到 25 依次編號（即，'a' -> 0, 'b' -> 1, 'c' -> 2, ... , 'z' -> 25）。

在一個 勻整 字串中，第 i 個字母的兩次出現之間的字母數量是 distance[i] 。如果第 i 個字母沒有在 s 中出現，那麼 distance[i] 可以 忽略 。

如果 s 是一個 勻整 字串，返回 true ；否則，返回 false 。

題解

主要的坑點在讀題，需要注意如果某個字串沒有出現過，那麼它的距離統統視為合法。

```cpp class Solution { public: bool checkDistances(string s, vector& distance) { map mp; for (int i = 0; i < s.length(); i++) { char c = s[i]; if (!mp.count(c)) mp[c] = i; else distance[c-'a'] -= (i - mp[c] - 1); }

    for (int i = 0; i < 26; i++) {
        if (distance[i] != 0 && mp.count('a'+i)) return false;
    }
    return true;
}

}; ```

恰好移動 k 步到達某一位置的方法數目

給你兩個 正 整數 startPos 和 endPos 。最初，你站在 無限 數軸上位置 startPos 處。在一步移動中，你可以向左或者向右移動一個位置。

給你一個正整數 k ，返回從 startPos 出發、恰好 移動 k 步併到達 endPos 的 不同 方法數目。由於答案可能會很大，返回對 109 + 7 取餘 的結果。

如果所執行移動的順序不完全相同，則認為兩種方法不同。

注意：數軸包含負整數。

題解

表面上看很容易想到搜尋或者是動態規劃，但實際上這是一道數學題。

由於我們只需要考慮可行解的數量，我們可以強行規定左邊的點是起點，右邊的點是終點。加上我們 知道了一共需要的步數k，所以我們可以算出向左、向右移動的步數。到這裡會發現這其實是一個組合問題，我們假設向左移動lef，向右移動rig。

那麼應該滿足lef + rig = k,start + rig - lef = end。這是一個很簡單的二元一次方程，求解即可。另外還需要注意，rig和lef都是非負整數。如果算出來是負數或者不為整數，說明無解。

求出了lef和rig之後，剩下的就是一個組合問題，我們要求的答案就是$C_k^{rig}$。

這裡有一個問題，由於答案可能很大，所以我們需要在計算的過程當中取模。但是組合數的運算會用到除法，但對於取模運算，除法不滿足結合律，即$a \bmod p * b \bmod p = ab \bmod p$，但是沒有$a \mod p \div b \bmod p \neq \frac a b \bmod p$。

要解決這個問題有兩種辦法，第一種辦法是通過$C_i^j = C_{i-1}^j + C_{i-1}^{j-1}$來推算，第二種辦法是求逆元。我們要求$\frac a b \bmod p$的結果，可以轉化成乘上$b$關於$a$和$p$的逆元。

這兩種方法都可以，我個人用的是逆元法。關於逆元的原理以及計算方法，這裡不做過多介紹了，大家感興趣可以查閱相關資料。

附上程式碼：

```cpp class Solution { public: typedef long long lint; void Exgcd(lint a,lint b,lint &x,lint &y){ if(!b) x=1,y=0; else Exgcd(b,a%b,y,x), y-=a/b*x; }

int inverse(lint a, lint p){
    lint x, y;
    Exgcd (a,p,x,y);
    x = (x%p+p)%p;
    return x; 
}

int numberOfWays(int st, int ed, int k) {
    int Mod = 1e9 + 7;
    int start = min(st, ed);
    int end = max(st, ed);

    int rig = end - start;
    int lef = k - rig;

    if (lef < 0 || lef % 2) return 0;
    rig += lef / 2;
    lint ret = 1;

    for (int i = 0; i < rig; i++) {
        ret = ret * (k - i) % Mod;
        ret = ret * inverse(i+1, Mod) % Mod;
    }

    return ret;
}

}; ```

最長優雅子陣列

給你一個由 正 整陣列成的陣列 nums 。

如果 nums 的子陣列中位於 不同 位置的每對元素按位 與（AND）運算的結果等於 0 ，則稱該子陣列為 優雅 子陣列。

返回 最長 的優雅子陣列的長度。

子陣列 是陣列中的一個 連續 部分。

注意：長度為 1 的子陣列始終視作優雅子陣列。

題解

這題題意裡藏著坑，主要是子陣列而非子序列，這兩者的意思完全不同。子序列可以不連續，但子陣列必須連續。

我們很容易發現，假設我們找到了一個完美子陣列，那麼這個子陣列內的任意兩個數的與值為0。轉化成二進位制，即這若干個數的每一個二進位制位最多隻有一個1。

有了這個限制條件之後很容易想到two pointers演算法，我們維護一段區間內所有二進位制位1的個數。如果新增一個數之後會導致某一位的個數大於1，那麼從左邊進行彈出操作，直到每一個二進位制位最多隻有一個1為止。

```cpp class Solution { public: // 將整數轉化成二進位制表示 vector to_bit(int x) { vector ret(33, 0); for (int i = 0; i < 32; i++) { if (x & (1 << i)) ret[i] = 1; } return ret; }

int longestNiceSubarray(vector<int>& nums) {
    int ret = 1;
    int l = 0, st = nums[0];
    int n = nums.size();
    // 存放當前區間內二進位制1的數量
    vector<int> bits = to_bit(nums[0]);

    for (int r = 1; r < n; r++) {
        vector<int> cur = to_bit(nums[r]);
        // 標記是否存在某一位的1的數量大於1
        bool flag = false;
        for (int i = 0; i < 32; i++) {
            bits[i] += cur[i];
            if (bits[i] > 1) flag = true;
        }
        while (flag) {
            cur = to_bit(nums[l]);
            flag = false;
            for (int i = 0; i < 32; i++) {
                bits[i] -= cur[i];
                if (bits[i] > 1) flag = true;
            }
            l++;
        }
        ret = max(ret, r - l + 1);
    }
    return ret;
}

}; ```

會議室 III

給你一個整數 n ，共有編號從 0 到 n - 1 的 n 個會議室。

給你一個二維整數陣列 meetings ，其中 meetings[i] = [starti, endi] 表示一場會議將會在 半閉 時間區間 [starti, endi) 舉辦。所有 starti 的值 互不相同 。

會議將會按以下方式分配給會議室：

  1. 每場會議都會在未佔用且編號 最小 的會議室舉辦。
  2. 如果沒有可用的會議室，會議將會延期，直到存在空閒的會議室。延期會議的持續時間和原會議持續時間 相同 。
  3. 當會議室處於未佔用狀態時，將會優先提供給原 開始 時間更早的會議。

返回舉辦最多次會議的房間 編號 。如果存在多個房間滿足此條件，則返回編號 最小 的房間。

半閉區間 [a, b) 是 a 和 b 之間的區間，包括 a 但 不包括 b 。

題解

模擬題，由於會議開始的時間各不相同，我們可以對會議進行排序，從最先開始的會議開始安排。

對於每一個會議，我們要找到最先空出來的會議室，如果有多個空的，我們選擇序號最小的。觀察一下資料範圍，會議最多是1e5個，會議室最多有100個。對於每個會議我們需要遍歷一次所有的會議室。那麼總的複雜度就是1e7，在可接受的範圍內。

當然如果想要優化也可以使用線段樹這樣的資料結構，可以把會議室的查詢降低到logN。但我個人感覺意義不大，大家如果感興趣可以看看大佬的部落格。

要注意會議延續的時間可能會很長，超過int的範圍，所以要用int64。

```cpp class Solution { public: int mostBooked(int n, vector>& meetings) { typedef long long lint; vector mst(n, 0), cnt(n, 0);

    const lint MAXI = 0x3f3f3f3f3f3f3f3f;
    sort(meetings.begin(), meetings.end());
    for (auto &vt: meetings) {
        lint sta = vt[0], end = vt[1];
        int choose = -1;
        lint mini = MAXI;
        bool not_exceed = false;
        for (int i = 0; i < n; i++) {
            if (mst[i] <= sta) {
                choose = i;
                not_exceed = true;
                break;
            }
            if (mst[i] < mini) {
                mini = mst[i];
                choose = i;
            }
        }

        if (not_exceed) {
            mst[choose] = end;
        }else {
            mst[choose] += end - sta;
        }

        cnt[choose] ++;
    }

    int mxi = -1, ret = -1;
    for (int i = 0; i < n; i++) {
        if (cnt[i] > mxi) {
            mxi = cnt[i];
            ret = i;
        }
    }
    return ret;
}

}; ```

「」
「」