略譯

原題目連結

有一台機器人站在數線原點 0
接下來他會依序收到並執行一連串指令
每個指令有三種可能：

• LEFT 代表往左走，位置-1
• RIGHT 代表往右走，位置+1
• SAME AS i 代表和第 i 個指令相同，i 一定是已執行過的指令
  問最後機器人所站的位置為何

題解

按照敘述模擬即可。

實作提示

• SAME AS i 其實沒有記錄的必要；
  直接記錄實際上的指令內容，可避免冗餘的查詢。
  • 最糟情況：
    • LEFT
    • SAME AS 1
    • SAME AS 2
    • SAME AS 3
    • …
    • SAME AS 99
  • 若一次次照著反查，則在第100項指令，會去看99，
    99看98，98看97，…
  • 讓看似 O(n) 的複雜度，在特定狀況下會劣化至 O(n^2)
    • 1+2+…+n => O(n^2)
  • 迴避方式：SAME AS 1實質上是LEFT，所以記錄LEFT；
    同理SAME AS 2實質上也是LEFT，記錄LEFT；
  • 最後記錄的情況將為：
    • LEFT
    • LEFT (原本為 SAME AS 1)
    • LEFT (原本為 SAME AS 2)
    • …
    • LEFT (原本為 SAME AS 99)
  • 如此一來，所有 SAME AS i 都可以在 O(1) 解決，
    整體複雜度會是 O(n)