star2dust

838. 推多米诺：一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。在开始时，我们同时把一些多米诺骨牌向左或向右推。每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。

给定表示初始状态的字符串 "S" 。如果第 i 张多米诺骨牌被推向左边，则 S[i] = 'L'；如果第 i 张多米诺骨牌被推向右边，则 S[i] = 'R'；如果第 i 张多米诺骨牌没有被推动，则 S[i] = '.'。

返回表示最终状态的字符串。

以下实例为小马智行（pony.ai）一面coding面试题。
输入：".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

// INPUT: |\ | /|||\ /||\ ||
// OUTPUT: \ | //|\ //\ ||

class Solution {
public:
    string pushDominoes(string dominoes) {
        //左右加上LR不影响最终结果，可以避免判定.是否在两端
        dominoes = "L"+dominoes+"R";
        string res = "";
        int n = dominoes.length(); 
        //双指针
        int left = 0, right = 1;
        while (right<n){
            if (dominoes[right]=='.') {
                //区块右边界更新
                right++;
                continue;
            }
            if (left>0){
                //LR不会改变，会改变的只有.
                res += dominoes[left];
            }
            int block_size = right-left-1;//区块中的.部分，不包括两端
            if (dominoes[left]==dominoes[right]){
                //左右相同，倒向相同
                res += string(block_size, dominoes[left]);
            }else if (dominoes[left]=='L' && dominoes[right]=='R'){//左右相异，分两种情况
                //左L右R，中间不变
                res += string(block_size,'.');
            }else{
                 //左R右L，二分点不变，左边变为R，右边变为L
                res += string(block_size/2,'R')+string(block_size%2,'.')+string(block_size/2,'L');
            }
            //区块左边界更新
            left = right;
            right++;
        }
        return res;
    }
};