2022.02.21

838.推多米诺

https://leetcode-cn.com/problems/push-dominoes/

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。
返回表示最终状态的字符串。

示例 1：

输入：dominoes = "RR.L"
输出："RR.L"
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：
示例2示意图

输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

提示：

n == dominoes.length
1 <= n <= 105
dominoes[i] 为 'L'、'R' 或 '.'

&emsp;学到的知识点：…
&emsp;看到这题最开始想的是就嗯模拟，想了想那样就O(n^2)时间了，于是想到用栈，栈中存储遍历到的最后一个R，但是实际上只需要存储一个R就行了，于是使用一个bool变量记录了上一个推的是不是R，并且根据遍历到的当前位置的不同推法，分为4种情况。
&emsp;代码如下：（C++）

class Solution {
public:
    string pushDominoes(string dominoes) {
        string ans=dominoes;
        int n=dominoes.size();
        bool last_is_right=false;//记录前一个推的是不是R
        int index=0;//记录“当前看来需要处理的序列的起始位置”
        if(ans[0]=='R'){
            last_is_right=true;
            index=1;
        }
        for(int i=1;i<n;i++){
            if(dominoes[i]=='L' && !last_is_right){
                for(int j=index;j<i;j++){
                    ans[j]='L';
                }
                index=i+1;
                last_is_right=false;
            }//如果当前位置是L且左边没有R，那么将左侧推成L
            else if(dominoes[i]=='L' && last_is_right){
                for(int j=index;j<(i-index)/2+index;j++){
                    ans[j]='R';
                }
                for(int j=(i-index)/2+index+(i-index)%2;j<i;j++){
                    ans[j]='L';
                }
                index=i+1;
                last_is_right=false;
            }//如果当前位置是L且上一个位置是R，那么按照奇偶来推，要处理的多米诺骨牌数量是奇数个的话，处理为L的位置要+1
            else if(dominoes[i]=='R'){
                if(last_is_right){
                    for(int j=index;j<i;j++){
                        ans[j]='R';
                    }
                }
                last_is_right=true;
                index=i+1;
            }//如果当前位置是R，那么看看左边要不要处理为R
            else{
                if(i==n-1 && last_is_right){
                    for(int j=index;j<n;j++){
                        ans[j]='R';
                    }
                }//末尾的骨牌处理
                //否则不做事
            }
        }
        return ans;
    }
};

&emsp;当然这些代码实际上没什么含金量，但是促使我写这篇博客的直接原因是我看到了这条评论：
@太阳家的猫：
Py3

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        od = ""
        while dominoes != od:
            od = dominoes
            dominoes = dominoes.replace("R.L", "T")
            dominoes = dominoes.replace(".L", "LL")
            dominoes = dominoes.replace("R.", "RR")
            dominoes = dominoes.replace("T", "R.L")
        return dominoes

&emsp;虽然这还是模拟，时间是O(n^2)，但是这代码实在是太漂亮了，我忍不住把它记录下来，我就是为了这瓶醋才包的这饺子。