友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
838. 推多米诺
n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡，该骨牌仍然保持不变。
就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。
给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：
-
dominoes[i] = L，表示第i张多米诺骨牌被推向左侧， -
dominoes[i] = R，表示第i张多米诺骨牌被推向右侧， -
dominoes[i] = .，表示没有推动第i张多米诺骨牌。
返回表示最终状态的字符串。
示例 1：
输入：dominoes = "RR.L" 输出："RR.L" 解释：第一张多米诺骨牌没有给第二张施加额外的力。
示例 2：
输入：dominoes = ".L.R...LR..L.." 输出："LL.RR.LLRRLL.."
提示：
-
n == dominoes.length -
1 <= n <= 105 -
dominoes[i]为L、R或.
思路分析
最初想的也是分类处理，过程向复杂了。
直接分成如下集中，再加上“哨兵”，处理起来就会很简单：
-
L..R这种两边倒，中间不受影响，无需处理。 -
L..L直接全部填L即可。 -
R..R直接全部填R即可。 -
R..L这种使用双指针从两端向中间夹逼即可。
在遍历过程中，直接处理，比最初设想的，把区间坐标成对保存下列，方便很多。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-29 22:40:19
*/
public String pushDominoes(String dominoes) {
char[] s = ("L" + dominoes + "R").toCharArray(); // 前后各加一个哨兵
int pre = 0; // 上一个 L 或 R 的位置
for (int i = 1; i < s.length; i++) {
if (s[i] == '.') {
continue;
}
if (s[pre] == s[i]) { // L...L 或 R...R
Arrays.fill(s, pre + 1, i, s[i]);
} else if (s[i] == 'L') { // R...L。注：L..R 这种情况不需要处理
int l = pre + 1, r = i - 1;
while (l < r) {
s[l] = s[l - 1]; // 前一半向右，变 R
s[r] = s[r + 1]; // 后一半向左，变 L
l++;
r--;
}
}
pre = i;
}
return new String(s, 1, s.length - 2); // 去掉前后哨兵
}