LEETCODE 解題紀錄 #2
838. Push Dominoes
└─解題難度：MEDIUM
近一個月來幾乎天天跟著 LeetCode 每日題跑，解題進度已經來到了 52 題，但紀錄卻只留下了一篇而已，有鑑於此，挑了昨天的題目來寫這篇文章囉。
其實心裡一直糾結什麼程度的題目才好拿上來寫紀錄，但或許這真的沒什麼好糾結的，反正也沒多少人在看 (誤)，寫什麼都好、都無所謂，有寫下來就對了。
題目說明
這題是給定某個時刻的骨牌狀態來推算最後穩定的狀態，以 R 表示被往右推的骨牌，以 L 表示被往左推的骨牌，. 表示直立的骨牌。
骨牌每秒只能影響其相鄰兩邊的牌，因此 R.. 在一秒後會變成 RR. 因為第一張牌往右倒下連帶推倒了第二張牌，第三張牌此時尚未受到第一張牌的作用，直到第二秒之後才會變成 RRR。
當 R 和 L 相遇時則會產生淨力平衡，例如 R..L 會以 RRLL 達到平衡，而 R...L 則會以 RR.LL 達到平衡，第三張牌維持直立是因為兩側骨牌同時傳遞到它，因此達成淨力平衡。
由於已經被推倒成為 R 或 L 的牌就不會再改變狀態了，因此可知我們只需要處理 . 的牌。
另外觀察 .R 或是 L. 可以發現這兩個也都處於淨力平衡，因此可以知道我們只需處理 R 右邊或是 L 左邊的 .。
解決方案
既然提到力平衡，我會想計算每一個點的淨力，即為左推力和右推力的和。兩力方向相反、差了一個負號，並且我需要一個計算推力大小的系統，滿足推力傳遞越遠、大小數值越低。
程式碼如下：
我以變數 c 表示推力大小，每當遇見推力源 ( R 或 L ) 我就將 c 初始化為骨牌的數量，而在推力源之後每當遇見 . 會傳播推力，推力會衰退，因此 c 遞減 1；每當遇見反向的推力源，則將推力大小歸零。
至於為什麼在推力源初始化為骨牌數量，這個設計是為了讓力傳播了所有骨牌之後依然為正，只是每傳遞一格數值遞減而已。
在第 8 行至第 17 行，我先由左向右計算右推力。
每遇到 . (第 9 行) 且當下右推力大於 0，則使右推力遞減；每遇到 R (第 11 行)則賦予一個大小等同於陣列大小的推力源，其餘 (也就是 L) 則將右推力歸零。
反之亦然，第 19 行至第 28 行反過來計算左推力，差別只在於遇到 L 就賦予推力源，遇到 R 就歸零，與前述步驟行為相反，並且正負號也相反，因此用減法將其併入 arr 中計算淨力。
以範例測資 LL.R 為例：
右推力 = 0 0 0 4
左推力 = -4 -4 0 0
------------------
淨推力 = -4 -4 0 4
L L . R以右為正，左為負，0 維持直立 (第 29 行)。因此可得平衡狀態 LL.R 。
另一筆測資 .L.R...LR..L.. ：
右推力 = 0 0 0 14 13 12 11 0 14 13 12 0 0 0
左推力 = -13 -14 0 0 -11 -12 -13 -14 0 -12 -13 -14 0 0
--------------------------------------------------------
淨推力 = -13 -14 0 14 2 0 -2 -14 14 1 -1 -14 0 0
L L . R R . L L R R L L . .得平衡狀態 LL.RR.LLRRLL.. 。
方法得證。
我在 LeetCode 上的程式碼基本上都放在下面這個 GitHub (除了早期有些用 iPad 寫的題目還沒更新到倉庫裡)，有興趣的人可以進去瞧瞧。
https://github.com/momocow/my-leetcodes/tree/master/problems
