【Leetcode 每日一题 - 补卡】838. 推多米诺

问题背景

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

• dominoes[i] = ‘L’，表示第 i 张多米诺骨牌被推向左侧，
• dominoes[i] = ‘R’，表示第 i 张多米诺骨牌被推向右侧，
• dominoes[i] = ‘.’，表示没有推动第 i 张多米诺骨牌。

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

数据约束

• $n=dominoes.length$
• $1\le n\le 10^5$
• $dominoes[i]$ 为 ‘L’、‘R’ 或 ‘.’

解题过程

需要考虑清楚的是，中间牌的变化，只与左右最近位置的 ‘L’ 或 ‘R’ 有关。
实际实现的时候，可以在两端增加不会影响结果的哨兵，把规律拓展到所有位置上。

具体实现

class Solution {public String pushDominoes(String dominoes) {char[] s = ("L" + dominoes + "R").toCharArray();int pre = 0;for (int i = 1; i < s.length; i++) {if (s[i] == '.') {continue;}if (s[i] == s[pre]) {Arrays.fill(s, pre + 1, i, s[i]);} else if (s[i] == 'L') {Arrays.fill(s, pre + 1, (pre + i + 1) / 2, 'R');Arrays.fill(s, (pre + i) / 2 + 1, i, 'L');}pre = i;}return new String(s, 1, s.length - 2);}
}