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好看多了