LeetCode周賽296，難度較低的新手練習場

語言: CN / TW / HK
時間 2022-06-07 12:15:22

大家好，日拱一卒，我是梁唐。本文始發於Coder梁

今天是週一，我們照慣例來看看昨天的LeetCode周賽。這次的周賽是上海諾基亞貝爾贊助的，我也不清楚諾基亞貝爾和諾基亞是什麼關係……這次的獎勵也很有意思，除了前200名有內推機會之外，前50名還能獲得校園學創班的機會……

這次的比賽的題目總體感覺比之前的幾場要簡單一些，考察的演算法偏基礎，總的說起來還是挺適合新人練手的。如果你對自己的演算法能力沒有信心的話，不妨嘗試著賽後練習一下，說不定這場比賽能夠幫你找到信心。

好了， 廢話就說到這裡，讓我們一起來看題吧。

極大極小遊戲

給你一個下標從 0 開始的整數陣列 nums ，其長度是 2 的冪。

對 nums 執行下述演算法：

  1. 設 n 等於 nums 的長度，如果 n == 1 ，終止 演算法過程。否則，建立 一個新的整數陣列 newNums ，新陣列長度為 n / 2 ，下標從 0 開始。
  2. 對於滿足 0 <= i < n / 2 的每個 偶數 下標 i ，將 newNums[i] 賦值 為 min(nums[2 * i], nums[2 * i + 1]) 。
  3. 對於滿足 0 <= i < n / 2 的每個 奇數 下標 i ，將 newNums[i] 賦值 為 max(nums[2 * i], nums[2 * i + 1]) 。
  4. 用 newNums 替換 nums 。
  5. 從步驟 1 開始 重複 整個過程。

執行演算法後，返回 nums 中剩下的那個數字。

題解

題目當中給的範圍非常小，最多隻有1024個數，那麼我們隨便怎麼玩都行。

直接按照題目的意思編寫邏輯即可，基本沒有難度。

比賽的時候，我腦抽了用的Python，其實C++也一樣實現。

```python class Solution: def minMaxGame(self, nums: List[int]) -> int: n = len(nums)

    while n > 1:
        news = []
        for i in range(n // 2):
            if i % 2 == 0:
                news.append(min(nums[i*2], nums[i*2+1]))
            else:
                news.append(max(nums[i*2], nums[i*2+1]))
        nums = news
        n = len(nums)
    return nums[0]

```

劃分陣列使最大差為 K

給你一個整數陣列 nums 和一個整數 k 。你可以將 nums 劃分成一個或多個 子序列 ，使 nums 中的每個元素都 恰好 出現在一個子序列中。

在滿足每個子序列中最大值和最小值之間的差值最多為 k 的前提下，返回需要劃分的 最少 子序列數目。

子序列 本質是一個序列，可以通過刪除另一個序列中的某些元素（或者不刪除）但不改變剩下元素的順序得到。

題解

這題本身其實難度並不大，但很容易給人誤導。比如我比賽的時候一直和子序列較勁，因為子序列要保證當中的元素相對順序和原來不變。所以當時本能地覺得排序這樣會打亂元素順序的操作鐵定不行，接著又要用到的序列儘量少，於是就想要貪心，每次建立一個區間，儘可能多地覆蓋剩餘的元素。

這樣當然是可以的，但極端case會超時。比如k等於0，並且陣列當中元素又各不相同的話， 我們需要建立n個區間，每次都要遍歷所有元素一次，顯然會超時。

就在我思考的時候，這道題已經通過了一千多人。那時候差不多才比賽剛開始15分鐘，我當時都要陷入自我懷疑了。後來稍微冷靜了一下，覺得一定是有什麼我沒有發現的trick。只要找到了trick，就看可以解決問題。

那麼trick在哪裡呢？在於題目的限制條件——子序列。表面上看子序列需要保證元素順序和原來一樣，但實際上在本題當中，子序列當中的相對順序並不重要，我們不關心子序列當中的元素是如何排列的，我們只關心要用到多少子序列。這個限制條件就是出題人的障眼法，置之不理就可以了。

一旦去掉這個限制，解法就呼之欲出了，我們直接把所有元素排序，然後從小到大遍歷一次，計算一下覆蓋需要的最少區間即可。

```cpp class Solution { public: int partitionArray(vector& nums, int k) { int n = nums.size();

    sort(nums.begin(), nums.end());

    int last = nums[0];
    int ret = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i] > last + k) {
            ret++;
            last = nums[i];
        }
    }
    return ret;
}

}; ```

替換陣列中的元素

給你一個下標從 0 開始的陣列 nums ，它包含 n 個 互不相同 的正整數。請你對這個陣列執行 m 個操作，在第 i 個操作中，你需要將數字 operations[i][0] 替換成 operations[i][1] 。

題目保證在第 i 個操作中：

  • operations[i][0] 在 nums 中存在。
  • operations[i][1] 在 nums 中不存在。

請你返回執行完所有操作後的陣列。

題解

看一眼資料範圍，元素數量以及運算元量都是1e5這個量級，顯然我們直接模擬是一定會超時的。

不難想到，不論如何操作，都不會改變元素的數量。那麼，即使我們操作m次，一個數改變了m次，我們也可以等價於看做是隻改變了一次。相當於我們把這m次操作進行了合併，合併成了一次操作。我們只需要得到這個合併之後的結果，再對陣列當中的元素進行一次操作即可。

所以所有的關鍵都在於操作的合併上，那麼怎麼進行合併呢？

不難發現，多次操作之間具有關聯關係。比如一次操作是將1變成3，第二次操作是將3變成2，那麼等價於將1變成2。那麼我們怎麼樣判斷這樣的關聯關係呢？難道要兩兩配對進行遍歷嗎？顯然這樣也會超時，我們可以使用map來儲存變化之間的關係。

對於一次操作，我們假設是從u變成了v。我們使用兩個map，一個的key是u，value是v，記錄u能變成v，我們把這個map叫做fwd(forward)。另外一個反過來，記錄v是由u得到的，這個map叫做bkd(backward)。

當我們遍歷得到一個新的操作(u, v)時，我們首先判斷bkd[u]是否存在，如果不存在，說明這個操作和之前的操作沒有任何關係，我們直接記錄：fwd[u]=v; bdk[v] = u。如果存在，那麼將fwd[bkd[u]] = v，並且更新bkd：bdk[v] = bkd[u]，最後刪除bdk[u]即可。

```cpp class Solution { public: vector arrayChange(vector& nums, vector>& operations) { map fwd, bkd; for (auto &op : operations) { int u = op[0], v = op[1]; if (bkd.count(u) == 0) { fwd[u] = v; bkd[v] = u; }else { int pu = bkd[u]; fwd[pu] = v; bkd[v] = pu; bkd.erase(u); } }

    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int u = nums[i];
        if (fwd.count(u)) nums[i] = fwd[u];
    }
    return nums;
}

}; ```

設計一個文字編輯器

請你設計一個帶游標的文字編輯器，它可以實現以下功能：

  • 新增：在游標所在處新增文字。
  • 刪除：在游標所在處刪除文字（模擬鍵盤的刪除鍵）。
  • 移動：將游標往左或者往右移動。

當刪除文字時，只有游標左邊的字元會被刪除。游標會留在文字內，也就是說任意時候 0 <= cursor.position <= currentText.length 都成立。

請你實現 TextEditor 類：

  • TextEditor() 用空文字初始化物件。
  • void addText(string text) 將 text 新增到游標所在位置。新增完後游標在 text 的右邊。
  • int deleteText(int k) 刪除游標左邊 k 個字元。返回實際刪除的字元數目。
  • string cursorLeft(int k) 將游標向左移動 k 次。返回移動後游標左邊 min(10, len) 個字元，其中 len 是游標左邊的字元數目。
  • string cursorRight(int k) 將游標向右移動 k 次。返回移動後游標左邊 min(10, len) 個字元，其中 len 是游標左邊的字元數目。

題解

這題花裡胡哨看起來好像很複雜，但實際上題意非常簡單，就是讓我們模擬生成一個編輯器。

做演算法題有一個小技巧， 題目比較長的問題不一定困難，往往反而比較簡單。因為題目越長說明給的資訊越多，題目的描述也越清楚。真正的難題反而很短，越短說明資訊量越凝練，需要我們做的分析和推理就越多。

回到問題，這題最大的難點在於我們輸入文字以及移動游標的時候會導致游標左右兩側內容的變化。如果我們使用字串來記錄游標左右兩側的內容的話，顯然這會非常影響效能。游標左側的字串還好，我們都是在它的末尾進行插入和刪除，我們可以把字串當做是vector進行push_back和pop_back，這些都是O(1)的操作。

對於游標右側的內容就比較麻煩了，我們需要在它的頭部進行操作。在一個數組頭部元素進行增刪是最麻煩的，需要移動整個陣列或者是拷貝整個陣列。

但我們分析一下題目就會發現，其實游標右側的內容我們只需要記錄下來即可，我們需要顯示的永遠只有游標左側的結果。所以我們可以將游標右側的文字進行反向儲存，比如LEET|CODE，這裡的|表示游標，那麼游標右側實際儲存的字串是EDOC。這樣當我們移動游標的時候，就等價於在陣列的末尾進行操作了。

其實這題考察的就是對於字串進行修改的複雜度的理解，只要利用pop_back和push_back都是O(1)的複雜度，就可以很輕易地解出這題。

```cpp class TextEditor { public:

string cl, cr;
int p;

TextEditor() {
    p = 0;
}

void addText(string text) {
    for (auto c : text) {
        cl.push_back(c);
    }
}

int deleteText(int k) {
    int ret = 0;
    // 刪除，等價於彈出游標左側的末尾元素
    for (int i = 0; i < k; i++) {
        if (cl.empty()) break;
        ret++;
        cl.pop_back();
    }
    return ret;
}

string cursorLeft(int k) {
    // 向左移動游標，等價於刪除游標左側的內容，插入到右側
    for (int i = 0; i < k; i++) {
        if (cl.empty()) break;
        char c = cl.back();
        cl.pop_back();
        cr.push_back(c);
    }

    string ret = "";
    for (int i = max((int) cl.size()-10, 0); i < cl.size(); i++) ret.push_back(cl[i]);
    return ret;
}

string cursorRight(int k) {
    // 向右移動游標，等價於彈出游標右側的內容，插入到左側
    for (int i = 0; i < k; i++) {
        if (cr.empty()) break;
        char c = cr.back();
        cr.pop_back();
        cl.push_back(c);
    }

    string ret = "";
    for (int i = max((int) cl.size()-10, 0); i < cl.size(); i++) ret.push_back(cl[i]);
    return ret;
}

};

/ * Your TextEditor object will be instantiated and called as such: * TextEditor obj = new TextEditor(); * obj->addText(text); * int param_2 = obj->deleteText(k); * string param_3 = obj->cursorLeft(k); * string param_4 = obj->cursorRight(k); / ```

怎麼樣，這周的題目基本上都沒有用到一些比較困難的演算法，大多是對一些基礎技能和知識的考量。

如果覺得不錯，不妨親自上手練一練吧~

「」
「」