image-20220221121105328

纯模拟，我的写法是加了一个左侧指针，官方解答是双指针或者BFS

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
class Solution:
  def pushDominoes(self, dominoes: str) -> str:
    length = len(dominoes)
    ans = ''
    i = 0
    p = -1
    c = '.'
    while i < length:
      if dominoes[i] == 'L':
        if c == 'R':
          if (i - p + 1) % 2:
            ans += 'R' * ((i - p - 2) // 2) + '.' + 'L' * ((i - p) // 2)
          else:
            ans += 'R' * ((i - p - 1) // 2) + 'L' * ((i - p + 1) // 2)
        else:
          ans += 'L' * (i - p)
        p = i
        c = 'L'
      if dominoes[i] == 'R':
        if c == 'R':
          ans += 'R' * (i - p - 1)
        else:
          ans += '.' * (i - p - 1)
        ans += 'R'
        p = i
        c = 'R'
      i += 1
    if c == 'R':
      ans += 'R' * (i - p - 1)
    else:
      ans += '.' * (i - p - 1)
    return ans

看到一个 nb 的代码，BFS的，思路很简单，虽然很慢，但是很 nb

1
2
3
4
5
6
7
8
9
10
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