Re: [閒聊] 每日LeetCode
838. Push Dominoes
推多米諾骨牌 給你初始狀態問最後的結果 R是向右倒 L向左 .是直立
不用考慮兩邊不同數量造成的力 意思就是 "RRRRRRRR.L" 也推不過去
Example 1:
Input: dominoes = "RR.L"
Output: "RR.L"
Example 2:
Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
思路:
1.最直觀的解法就是一回合一回合模擬 每回合只更新LR左右的.的狀態
遇到R.L就不動 R.就變成RR .L就變成LL 要注意的就是.的狀態更新後不能去推其他.
不然遇到 "R....L" 會變成 "RRRR.L"
因為一次只推一個 時間複雜度很差 O(n^2)
2.接下來就想 有沒有辦法直接知道每個.結束的狀態? 有
因為.狀態改變之後就固定了 所以就是看R和L哪個能先碰到他
也就是看他左邊最近的R和右邊最近的L 哪個離他比較近
先對每個點算出這兩個的值 都O(n) 最後再掃一次更新狀態
3.code寫的好長好醜就不貼了
4.看discuss才發現其實不用這麼麻煩 直接從左掃到右 遇到.就先跳過
遇到 L....L 的話 回頭把中間全部取代成L 遇到R....R的話 回頭把中間全部取代成R
遇到 L....R 的話 中間不用動 不會被影響到了
遇到 R....L 的話 左半邊R 右半邊L
還能分別在頭尾插L和R 讓寫法更漂亮
5.幹我的code真的好醜
6.其實直接模擬也能過
class Solution:
def pushDominoes(self, dominoes: str) -> str:
while(True):
new = dominoes.replace('R.L', 'S')
new = new.replace('.L','LL').replace('R.','RR')
if new == dominoes:
break
else:
dominoes = new
return dominoes.replace('S', 'R.L')
比我的醜code好看多了
--
沒人在乎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.233.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664293253.A.13A.html
→
09/27 23:41,
1年前
, 1F
09/27 23:41, 1F
→
09/27 23:41,
1年前
, 2F
09/27 23:41, 2F
→
09/27 23:42,
1年前
, 3F
09/27 23:42, 3F
討論串 (同標題文章)
完整討論串 (本文為第 12 之 719 篇)：
閒聊
1
3