前往
大廳
主題

LeetCode - 838. Push Dominoes 解題心得

Not In My Back Yard | 2021-11-28 00:00:05 | 巴幣 0 | 人氣 112

題目連結:


題目意譯:
現在有 n 個多米諾骨牌排於一列,而我們將每個骨牌垂直擺放。一開始,我們同時地往左或往右地推動其中一些骨牌。

每經過一秒,每個往左傾倒的骨牌將會推動其左側相鄰之骨牌。相似地,每個往右傾倒的骨牌將會推動其右側相鄰站立之骨牌。

當一個直放著的骨牌兩側都有骨牌傾倒到它身上時,它將因為力平衡而維持不動。

對於此問題,我們將一個傾倒的骨牌視為不會再施加其他的力量於其他傾倒或是已經倒下的骨牌。

你被給定一個字串 dominoes 代表初始狀態,其中:
dominoes[i] = 'L',如果第 i 個骨牌被推向左側、
dominoes[i] = 'R',如果第 i 個骨牌被推向右側、
dominoes[i] = '.',如果第 i 個骨牌沒有被推動。

回傳一字串代表著最終狀態。

限制:
n == dominoes.length
1 ≦ n ≦ 10 ^ 5
dominoes[i] 只會是 'L' 、 'R' 或是 '.'。



範例測資:
範例 1:
輸入: dominoes = "RR.L"
輸出: "RR.L"
解釋: 第一個骨牌不會施加額外的力於第二個骨牌上。

範例 2:
輸入: dominoes = ".L.R...LR..L.."
輸出: "LL.RR.LLRRLL.."


解題思維:
模擬即可。

我們掃過 dominoes 陣列,並利用一個變數 X 來儲存目前看到「前一個」 'R' 所在之位置(X 一開始設為 -1,代表目前沒有 'R')。

當 dominoes[i] 為 'L' 且 X 不為 -1 時,也就是代表有先前的 R 可以與之這個 L 配對。因此直接從我們可以直接模擬從 X 這個位置往右倒(也就是字元 'R' 將從 X 往右延伸)以及從 i 這個位置往左倒,直到兩者跑到相同的位置或是穿過彼此。

而當 dominoes[i] 為 'L' 但是 X 為 -1 時,那就直接從 i 這個位置往左倒直到碰到不是 '.' 的字元或是超過開頭為止(因為此時代表左邊的骨牌要嘛已經倒過,所以不需再次倒下、要嘛根本就沒有左邊了)。

而當 dominoes[i] 為 'R' 且 X 不為 -1 時,那我們可以從 X 往右倒到 i - 1 為止。並將 X 之值更新為 i。

最後掃完後如果 X 不為 -1,那就繼續往右倒直到碰到結尾。此時,過程中造成的傾倒之狀態即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作