838_推多米诺

难度：中等

题目

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

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

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

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

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

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

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

示例

示例一：

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

示例二：

img

输入：dominoes = “.L.R…LR..L..”
输出：”LL.RR.LLRRLL..”

提示

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

解题

最直观的想法就是找到每个状态为直立的骨牌，然后比较它前后两块的状态

1
2
3
4
5
char cur = sb.charAt(i);
if (cur != '.') {
  pre = cur;
  continue;
}
  • 如果前后都为 L，则它会变成 L
  • 如果前后都是 R，则它会变成 R
  • 如果前为 R，后为 . ，则它会变成 R
  • 如果后为 L，前为 . ，则它会变成 L

如果为边界，则认为是直立状态。如左边界前一个为直立，右边界后一个位直立。

char next = i==n-1?'.':sb.charAt(i+1);

1
2
3
4
5
6
7
8
9
if (pre=='R'&&next!='L'){
  // 左侧 R，右侧为 R 或者 . 向右倒
  hasChange = true;
  sb.setCharAt(i,'R');
} else if (next=='L'&&pre!='R'){
  // 右侧为 L，左侧为 L 或者 . 向左倒
  hasChange = true;
  sb.setCharAt(i,'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
27
28
29
30
31
32
33
public String pushDominoes(String dominoes) {
  int n = dominoes.length();
  StringBuilder sb = new StringBuilder(dominoes);
  while (true){
    boolean hasChange = false;
    char pre = '.';
    for (int i=0; i<n; i++){
      // 当前位置
      char cur = sb.charAt(i);
      if (cur != '.') {
        pre = cur;
        continue;
      }
      // 下一个位置
      char next = i==n-1?'.':sb.charAt(i+1);
      if (pre=='R'&&next!='L'){
        // 左侧 R，右侧为 R 或者 . 向右倒
        hasChange = true;
        sb.setCharAt(i,'R');
      } else if (next=='L'&&pre!='R'){
        // 右侧为 L，左侧为 L 或者 . 向左倒
        hasChange = true;
        sb.setCharAt(i,'L');
      }
      pre = cur;
    }
    // 每次迭代如果没有变化，则说明稳定，结束
    if (!hasChange){
      break;
    }
  }
  return sb.toString();
}