Leetcode 838. Push Dominoes_综合

文章作者：Tyan
博客：noahsnail.com | CSDN | 简书

1. Description

Push Dominoes

2. Solution

**解析：**两种思路，一种思路是对所有的.，判断是否替换，如果需要替换，根据可能的情况分析替换成L还是R，通过左右双指针实现。一种思路是对所有的L和R，替换其附近需要替换的.，首先，对于L左边没有R的情况，替换.为L，对于R右边不存在L的情况，替换.为R；对于R右边存在L的情况，R和L正中间的.保持不变，左半部分变为R，右边部分变为L，循环从L的下一位重新开始。

Version 1

class Solution:def pushDominoes(self, dominoes: str) -> str:n = len(dominoes)state = list(dominoes)for i in range(n):if state[i] == '.':left = i - 1right = i + 1while left > -1 and dominoes[left] == '.':left -= 1while right < n and dominoes[right] == '.':right += 1if left != -1 and right != n:if dominoes[left] == 'R' and dominoes[right] == 'L':if i - left > right - i:state[i] = 'L'elif i - left < right - i:state[i] = 'R'elif dominoes[left] == 'R' and dominoes[right] == 'R':state[i] = 'R'elif dominoes[left] == 'L' and dominoes[right] == 'L':state[i] = 'L'elif right != n and dominoes[right] == 'L':state[i] = 'L'elif left != -1 and dominoes[left] == 'R':state[i] = 'R'return ''.join(state)

Version 2

class Solution:def pushDominoes(self, dominoes: str) -> str:n = len(dominoes)state = list(dominoes)i = 0while i < n:if dominoes[i] == 'L':left = i - 1while left > -1 and dominoes[left] == '.':state[left] = 'L'left -= 1elif dominoes[i] == 'R':right = i + 1while right < n and dominoes[right] == '.':state[right] = 'R'right += 1if right != n and dominoes[right] == 'L':for k in range(right - (right - i - 1) // 2, right):state[k] = 'L'if (right - i - 1) % 2 == 1:state[i + (right - i - 1) // 2 + 1] = '.'i = righti += 1return ''.join(state)

Reference

https://leetcode.com/problems/push-dominoes/