Сложность: medium
Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.
В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.
Пример:
Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
👨💻 Алгоритм:
1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы.
2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.
3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам.
😎 Решение:
class Solution:
def pushDominoes(self, dominoes: str) -> str:
N = len(dominoes)
indexes = [-1]
symbols = ['L']
for i in range(N):
if dominoes[i] != '.':
indexes.append(i)
symbols.append(dominoes[i])
indexes.append(N)
symbols.append('R')
ans = list(dominoes)
for idx in range(len(indexes) - 1):
i, j = indexes[idx], indexes[idx + 1]
x, y = symbols[idx], symbols[idx + 1]
if x == y:
for k in range(i + 1, j):
ans[k] = x
elif x == 'R' and y == 'L':
for k in range(i + 1, j):
if k - i == j - k:
ans[k] = '.'
elif k - i < j - k:
ans[k] = 'R'
else:
ans[k] = 'L'
return ''.join(ans)
Ставь 👍 и забирай 📚 Базу знаний