You are given an integer array deck
. There is a deck of cards where every card has a unique integer. The integer on the card is deck[i]
.
You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.
You will do the following steps repeatedly until all cards are revealed:
Return an ordering of the deck that would reveal the cards in increasing order.
Note that the first entry in the answer is considered to be the top of the deck.
Example 1:
deck = [17,13,11,2,3,5,7]
[2,13,3,11,5,17,7]
[17,13,11,2,3,5,7]
(this order does not matter), and reorder it.[2,13,3,11,5,17,7]
, where 2 is the top of the deck.[3,11,5,17,7,13]
.[5,17,7,13,11]
.[7,13,11,17]
.[11,17,13]
.[13,17]
.[17]
.Example 2:
deck = [1,1000]
[1,1000]
Constraints:
deck.length
<= 1000deck[i]
<= deck
are unique.這題是使用到 deque,Python 中的 deque 其實就是支援兩邊 append 和 pop 的好工具,以往的 append 只能從尾巴加上去,現在有 appendleft 可以用,而以往 pop 只能從尾巴 pop,現在有 popleft 可以用,底層實作應該是多幾支 pointer 穰我快速指過去而已,總之比較方便,耶!
今天就避免不了 simulation,仔細看題目說他會抽牌,然後把 top 移到 deck 下方,要直接使用 counting 把結果寫出來有點困難,而使用 simulation 也無從得知 deck 順序,唯一知道順序的是抽卡順序要由小到大,那就從這部分下手,而我要做的就是 "ex-simulation",反模擬就可以了
原先題目是說「先抽卡再將 top 移到底部」,反模擬就把手牌當作另一個 deck,將手牌先蓋牌,然後再移動 buttom 至 top 就可以了
來看看程式碼:
第 3 - 4 行:創建手牌,也就是透過 deque,但因為等等要依序丟到 deck 中,所以 sorting 要 reverse 過
第 5 行:創建 deque
第 7 - 11 行:模擬放牌、移牌階段,注意要 append 到最左邊,也就是蓋到 deck 最上方
第 12 - 14 行:要把 deque 轉回 list,所以重新一個一個 append 上去 ans
複雜的時間主要在模擬那一段,但因為 deque 幫我把所有 append 和 pop 都用 時間做到,所以複雜度會是外層模擬的
空間複雜度會在 deque 身上,所以是