LeetCode周賽301，離大譜，手速場掉分，質量場掉大分……

語言: CN / TW / HK
時間 2022-07-13 03:16:44

大家好，我是樑唐。

今天是週一，我們來看下昨天的LeetCode周賽。

這一次是周賽第301場，這一場由中國銀聯贊助。前500名都有內推的機會，離譜的是老樑我剛好第502名……

這一次的題目質量不錯，比之前提升了不少。個別題目還是有一定難度，雖然沒有用到高階的演算法，但是需要仔細思考才能想出解法。非常適合大家練習。

比賽結束之後看到評論區裡有人吐槽，把我逗得不行……

image-20220711110438121

好了，閒言少敘，進入正題，來看看這次的賽題吧。

裝滿杯子需要的最短總時長

現有一臺飲水機，可以製備冷水、溫水和熱水。每秒鐘，可以裝滿 2 杯 不同 型別的水或者 1 杯任意型別的水。

給你一個下標從 0 開始、長度為 3 的整數陣列 amount ，其中 amount[0]、amount[1] 和 amount[2] 分別表示需要裝滿冷水、溫水和熱水的杯子數量。返回裝滿所有杯子所需的 最少 秒數。

題解

怎麼樣，第一題是不是就來了個下馬威？

看著題目很簡單，但是真上手去做，還是要想一想。由於只有三個杯子，我們可以先對這三個杯子的容積進行排序。我們把排序之後的三個杯子從小到大分別叫做A、B、C。

首先觀察幾個例子就可以發現，當這三個杯子大小關係不同時，我們採取的策略也是不同的。比如如果C容積很大，要大於A+B的話，那麼最佳策略當然是A和B分別和C一起灌水，最後C剩餘的部分再單獨裝。這種情況的答案就是C。

C < A+B時，我們就需要換一種策略。A和B在與C裝水的時候，要儘量保證A和B剩餘的容積儘可能相同，這樣的話，我們就可以在裝滿C之後，同時裝A和B，來節省時間。我們把C裝滿時裝入A和B的水也是C，A和B剩餘要裝的水量是A+B-C，在我們的操作下，它儘量平均地分配在A和B兩個杯子中，所以剩餘的時間就是(A+B-C)/2。這裡要注意，A+B-C的奇偶性，如果是奇數，那麼答案還需要再加上1。

程式碼如下：

cpp class Solution { public: int fillCups(vector<int>& am) { sort(am.begin(), am.end()); int ret = 0; if (am[0] + am[1] <= am[2]) { return am[2]; } return (am[0] + am[1] - am[2] + 1) / 2 + am[2]; } };

無限集中的最小數字

現有一個包含所有正整數的集合 [1, 2, 3, 4, 5, ...] 。

實現 SmallestInfiniteSet 類：

  • SmallestInfiniteSet() 初始化 SmallestInfiniteSet 物件以包含 所有 正整數。
  • int popSmallest() 移除 並返回該無限集中的最小整數。
  • void addBack(int num) 如果正整數 num 不 存在於無限集中，則將一個 num 新增 到該無限集中。

題解

這題的範圍很小，即使是$O(n^2)$的時間複雜度或空間複雜度都沒有關係。並且最大的資料範圍只有1000，我這裡直接用了一個長度為1000的陣列來標記一個數字有沒有被刪除掉，用一個標記l來記錄當前存在的最小元素。

在popSmallest操作的時候，通過迴圈尋找下一個沒有被刪除的元素。在addBack的時候，修改對應的標記即可。

```cpp class SmallestInfiniteSet { public:

vector<int> nums;
int l;

SmallestInfiniteSet() {
    nums = vector<int>(1005, 1);
    l = 1;
}

int popSmallest() {
    int ret = l;
    nums[l] = 0;
    for (int i = l+1; i < 1001; i++) {
        if (nums[i] == 1) {
            l = i;
            break;
        }
    }
    return ret;
}

void addBack(int num) {
    if (num < l) l = num;
    nums[num] = 1;
}

};

/ * Your SmallestInfiniteSet object will be instantiated and called as such: * SmallestInfiniteSet obj = new SmallestInfiniteSet(); * int param_1 = obj->popSmallest(); * obj->addBack(num); / ```

移動片段得到字串

給你兩個字串 start 和 target ，長度均為 n 。每個字串 僅 由字元 'L'、'R' 和 '_' 組成，其中：

  • 字元 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左側直接存在一個 空位 時才能向 左 移動，而片段 'R' 只有在其右側直接存在一個 空位 時才能向 右 移動。
  • 字元 '_' 表示可以被 任意 'L' 或 'R' 片段佔據的空位。

如果在移動字串 start 中的片段任意次之後可以得到字串 target ，返回 true ；否則，返回 false 。

題解

這一題乍一看題是有點難的，因為涉及到字串的處理，而且字母還可以移動，疊加在一起看起來有些棘手。

但是我們稍微分析一下會發現題目中的限制其實還是挺明顯的，因為L只能往左，R只能往右，字母之間不能交叉。所以我們只需要判斷在L只能往左，R只能往右的前提下，start能否變成target即可。

具體怎麼判斷呢？我們遍歷start和target中的每一個字母進行比對。首先要這兩個字元相等，其次在L只能往左，R只能往右的前提下，判斷start中的字元能否移動到target中同樣的位置。比如同樣的L，如果start中的L在target中的左側，那麼就不能成立，因為L不能往右移動。R也是同理。

這裡，我使用了兩個pair<int, char>的vector來分別記錄了start和target中的每一個字元以及它的位置。接著再來分別判斷，每一個字元是否相同，並且能否通過移動到達同樣的位置。

```cpp class Solution { public: bool canChange(string st, string tt) { typedef pair pic; vector vs, vt;

    int n = st.length();
    for (int i = 0; i < n; i++) {
        if (st[i] == 'L' || st[i] == 'R') {
            vs.push_back(make_pair(i, st[i]));
        }
        if (tt[i] == 'L' || tt[i] == 'R') {
            vt.push_back(make_pair(i, tt[i]));
        }
    }

    int m = vs.size();
    if (vs.size() != vt.size()) return false;
    for (int i = 0; i < m; i++) {
        if (vs[i].second != vt[i].second) {
            return false;
        }

        if (vs[i].second == 'L') {
            if (vs[i].first >= vt[i].first)
                vs[i].first = vt[i].first;
            else
                return false;
        }
        if (vs[i].second == 'R') {
            if (vs[i].first <= vt[i].first)
                vs[i].first = vt[i].first;
            else
                return false;
        }
    }
    return true;
}

}; ```

統計理想陣列的數目

給你兩個整數 n 和 maxValue ，用於描述一個 理想陣列 。

對於下標從 0 開始、長度為 n 的整數陣列 arr ，如果滿足以下條件，則認為該陣列是一個 理想陣列 ：

  • 每個 arr[i] 都是從 1 到 maxValue 範圍內的一個值，其中 0 <= i < n 。
  • 每個 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。

返回長度為 n 的 不同 理想陣列的數目。由於答案可能很大，返回對 109 + 7 取餘的結果。

題解

這題簡直了，難度有點太大了，我賽後推導了半天，感覺不是很適合比賽。但即使這樣，仍然有很多大佬在賽中做出了這題，怎麼說呢，給跪一個吧……

我們很容易找到狀態轉移，如果我們以dp[i][j]表示以i開頭長度為j的陣列的數量。那麼對於dp[i][j+1]來說，它等於[1, maxValue]這個區間當中所有能被i整除的k對應的dp[k][j]的和。

這個結論是怎麼得到的呢？很簡單，當k能被i整除時，意味著我們可以在數字k之前放入一個i，並且得到的陣列依然是完美的。對於所有能夠被i整除的k我們都能這麼幹。

這個狀態轉移方程相對來說還比較容易發現，但是發現了它並沒有卵用。因為在本題當中狀態數和轉移數的數量都非常大，這麼搞鐵定超時。

那還有什麼其他的辦法嗎？

我們可以反其道行之，思考以i結尾的情況。對於以i結尾的完美陣列來說，i之前的可以放的數也是確定的，它們都必須是i的因子。我們可以通過分解質因數的方式找出i所有的因子，並且可以保證i的因子數量不會超過$\log i$ 這個範圍。

這裡面有一個問題，比如說當i是6時，2和3都是它的因子，但2不能和3同時出現在同一個陣列當中。因為2不是3的因子。這就使得我們需要對這些因子進行分類，怎麼分類呢，按照質因數分類，分別計算完美陣列的數量。最後再把這些所有的情況乘起來。

假設，現在我們知道了數字i某一個質因數$p$的冪是k，我們怎麼求它對應的完美陣列的數量呢？

我們可以先試著寫出數列：

$$ a_1, a_2, \cdots, a_n $$

其中$a_n = p^m$，因為我們要保證陣列的最後一個數是i。因為這個數列當中都是$p$的冪，我們可以進一步簡化一下，把底數去掉，只看指數。並且這個數列還存在大小關係：

$$ 0 \le a_1 \le a_2 \le \cdots \le a_n = k $$

我們怎麼求滿足條件的數列的總數呢？

這需要經過一系列的變形，我們令$a_0 = 0$，接著，我們將數列中的元素兩兩作差之後再求和，可以得到：

$$ (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + \cdots + (a_n - a_{n-1}) = a_n - a_0 = a_n = k $$

我們令$b_1 = a_1 - a_0+1, b_2 = a_2 - a_1+1, \cdots b_n = a_n - a_{n-1}+1$，於是我們得到了一個全新的數列$b$,那麼$\sum_{i=1}^nb_i = n+k$

由於$a$數列不遞減，所以$b_i \in[1, k+1]$，$b$數列的數量就是對應的$a$數列的數量。$b$數列怎麼求呢？我們可以轉化成盒模型求解，$b$數列的數量求解等價於這個問題：我們當前有$n$個盒子，有$n+k$個球要放入盒中，要保證每個盒子裡至少有一個球，一共有多少種？

求這個問題很簡單，我們可以把這$n+k$個球排成一排，一共有$n+k-1$個間隔。我們從中任選$n-1$個間隔，可以將球分成$n$堆。並且每一堆球的數量至少是一個，且總和剛好等於$n+k$。我們從$n+k-1$個間隔當中任選$n-1$個，一共有$C_{n+k-1}^{n-1}$種可能。

在本題當中由於$n$很大，求解$C_{n+k-1}^{n-1}$可能會超時，我們可以將其轉化成$C_{n+k-1}^k$來求解。$k$是質因數的冪，由於$maxValue$不會超過10000，可以保證$k$不會超過16。

另外，由於我們要計算組合數，還需要取模，由於組合公式當中存在除法。在有除法的取模運算當中需要計算逆元。或者我們可以使用組合$C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$的性質來計算，可以規避掉需要算逆元的問題。

在分解質因數的時候我用到了篩法，這不是必須的，因為本題資料範圍不大。

完整程式碼如下：

```cpp class Solution { public:

// 篩法求質數
void get_prime(vector<int> &prime, int m) {
    vector<bool> p(m+1, 1);
    for (int i = 2; i <= m; i++) {
        if (p[i]) prime.push_back(i);
        for (int j = i + i; j <= m; j += i) p[j] = false;
    }
}

// 分解質因數
vector<int> factorial(vector<int> &prime, int n) {
    vector<int> ret;
    for (auto p: prime) {
        int cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt ++;
        }
        if (cnt > 0) ret.push_back(cnt);
    }
    return ret;
}

int idealArrays(int n, int m) {
    long long Mod = 1e9 + 7;

    vector<int> prime;
    get_prime(prime, m);

    vector<vector<long long>> cmb(n+20, vector<long long>(20, 0));

    // 處理組合數
    cmb[1][0] = cmb[1][1] = 1;
    for (int i = 2; i < n+20; i++) {
        cmb[i][0] = 1;
        for (int j = 1; j < 16 && j <= i; j++) {
            cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1]) % Mod;
        }
    }

    long long ret = 1;

    for (int i = 2; i <= m; i++) {
        long long cur = 1;

        vector<int> fac = factorial(prime, i);
        for (auto x: fac) {
            cur *= cmb[n+x-1][x];
            cur %= Mod;
        }

        ret = (ret + cur) % Mod;
    }

    return ret;
}

}; ```

最後一題程式碼量並不算大，但是難度不小。思路不是非常清晰，需要彎好幾個彎不說，在求解的過程當中還會遇到很多阻礙需要解決，進一步增加了難度。

做這樣的難題雖然會掉頭髮，但是也的確學到很多，很鍛鍊人。我也很久沒有在LeetCode當中做過這樣的難題了，真的很酸，也很爽。尤其是最後做出來的時候，成就感還是非常強烈的。

關於這次的周賽就先聊到這裡，感謝大家的閱讀。

「」
「」