↓快轉到主要內容
  1. Leetcode/

[LeetCode] 950. Reveal Cards in Increasing Order

·
LeetCode sort queue simulation
目錄

題目連結：950. Reveal Cards in Increasing Order

解題思路
#

這題的題目敘述我一開始看的霧煞煞，感覺敘述的不是很清楚。這邊再重新整理一下題目的要求：

給定一個未經過排序的陣列，代表牌組，牌組的數字皆不重複。在開始翻牌前可以對牌組做任意的排序。之後開始使用以下步驟將牌翻開：

  1. 將牌頂的第一張牌翻開，然後將它從牌組中移除。
  2. 接著將下一張牌頂的牌放到牌底。
  3. 重複以上步驟直到全部的牌都被翻完。

題目的要求是找出一個正確的牌組排序方法，讓翻開的牌以遞增的方式排序。

理解題目的意思後就簡單了，就是個佇列的模擬問題，照著翻牌的步驟回推原本牌組的順序即可：

  1. 先將原始牌組排序，然後初始化一個雙向佇列(deque)。
  2. 接著將排序過後的牌組從大到小進行迭代新增進這個佇列：
    1. 首先先將佇列尾端的數字 pop 出來，再 push 到佇列的頂端。
    2. 將目前迭代到的牌 push 到佇列的頂端。

程式碼
#

C++
#

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        deque<int> dq;
        sort(deck.begin(), deck.end());
        for (auto it = deck.rbegin(); it != deck.rend(); it++) {
            if (!dq.empty()) {
                int bottom = dq.back(); dq.pop_back();
                dq.push_front(bottom);
            }
            dq.push_front(*it);
        }
        return vector<int>(dq.begin(), dq.end());
    }
};

Python
#

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        n = len(deck)
        res = []
        deck.sort()
        for i in reversed(range(n)):
            if res:
                res.insert(0, res.pop())
            res.insert(0, deck[i])
        return res