ETH官方钱包

創(chuàng)作內(nèi)容

1 GP

[leetcode]838. Push Dominoes

作者:???\~O_O~/???│2021-07-21 17:34:19│巴幣:2│人氣:153
題目: 838. Push Dominoes
難度: Medium

說明:
給你一個長度n的字串陣列代表一排連續(xù)骨牌的狀態(tài),字串當中只會有 '.' , 'L' , 'R' ,分別代表 "站著" , "向左倒" , "向右倒"
每秒更新一次狀態(tài),站著的骨牌(.)會被旁邊的骨牌推倒,並且會是以下三種其中之一的狀況:
1. 被其右邊向左倒的骨牌(L)推倒,並且接下來會向左倒(L)
2. 被其左邊向右倒的骨牌(R)推倒,並且接下來會向右倒(R)
3. 若其兩側(cè)的骨牌皆向他倒下,則它因例平衡而不會動(.)

求骨牌最後的狀態(tài)


解法: 狀態(tài)模擬(不良示範)

解法步驟:
0. 定義以下所說的"變化": 骨牌狀態(tài)從 '.' 變成 'L' 或 'R'
1. 需要更新的部分只有新的L與R,一開始給的算是新的。
2. 變化的骨牌不會再變化,並且只看其兩側(cè),故最多變化n次,即n次判斷該骨牌的下個狀態(tài)。
3. 依據(jù)變化的部分要求得"新"變化,變化需要知道骨牌兩側(cè)的狀態(tài),故需要一個供快速查找的容器或方法。
4. 每次更新只記錄"新"變化的部分,再依據(jù)"新"變化的部分更新狀態(tài)。
5. 將舊變化清空,新舊變化的指標互換,回到3。循環(huán)直到?jīng)]有新的變化。


對,這題模擬可以過,神奇。


應該是每根去看:
1. 他左邊,且最近,且會倒,且是往右倒的,距離他多遠。可做到 O(1)。
2. 他右邊,且最近,且會倒,且是往左倒的,距離他多遠。可做到 O(1)。
3. O(1) 算他最後狀態(tài)
4. 所以這題O(n)

source code

引用網(wǎng)址:http://www.jamesdambrosio.com/TrackBack.php?sn=5215047
All rights reserved. 版權(quán)所有,保留一切權(quán)利

相關(guān)創(chuàng)作

同標籤作品搜尋:leetcode|medium|C++

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

1喜歡★agold404 可決定是否刪除您的留言,請勿發(fā)表違反站規(guī)文字。

前一篇:agold404@巴哈 ... 後一篇:[leetcode]32...


face基於日前微軟官方表示 Internet Explorer 不再支援新的網(wǎng)路標準,可能無法使用新的應用程式來呈現(xiàn)網(wǎng)站內(nèi)容,在瀏覽器支援度及網(wǎng)站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現(xiàn)和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業(yè)系統(tǒng)版本才可使用)

face我們了解您不想看到廣告的心情? 若您願意支持巴哈姆特永續(xù)經(jīng)營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】