0838. 推多米诺
https://leetcode-cn.com/problems/push-dominoes/
一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
在开始时，我们同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。
给定表示初始状态的字符串 "S" 。如果第 i 张多米诺骨牌被推向左边，则 S[i] = 'L'；如果第 i 张多米诺骨牌被推向右边，则 S[i] = 'R'；如果第 i 张多米诺骨牌没有被推动，则 S[i] = '.'。
返回表示最终状态的字符串。
示例 1：
输入：".L.R...LR..L.."
输出："LL.RR.LLRRLL.."
示例 2：
输入："RR.L"
输出："RR.L"
说明：第一张多米诺骨牌没有给第二张施加额外的力。
提示：
0 <= N <= 10^5
表示多米诺骨牌状态的字符串只含有 'L'，'R'; 以及 '.';
- 双指针
- 哨兵
- 暂无
首先最终的 dominoes 状态一定满足：
- 如果该 domino 受力了（L 或者 R），那么最终状态一定是受力的状态。比如 domino 受力为 L，那么最终状态一定也是 L，R 也是同理。
- 如果一个 domino 没有受力，那么其可能保持原样，也可能由于其他 domino 而导致其变为 L 或者 R
因此我们只需要探究字符串 dominoes 中的 "." 在最终是 L 还是 R 即可。这里有一个关键点：只有相邻的受力 dominoes 才会相互影响。比如 .L...R..L 那么：
- 只有第一个 L 和 R 有可能有影响
- R 和第二个 L 有影响
- 第一个 L 和 第二 个 L 没有影响，因为二者并不相邻
想清楚这些，我们的算法就比较简单了。
我们可以使用双指针。其中：
- 左指针指向第一个受力 domino
- 右指针指向下一个受力 domino
左指针和右指针之前的 domino（一定是 .），最终的状态由左右指针指向而定。
具体地：
- 如果左指针是 L，右指针是 R，那么中间保持 . 不变
- 如果左指针是 L，右指针是 L，那么中间都 是 L
- 如果左指针是 R，右指针是 R，那么中间都是 R
- 如果左指针是 R，右指针是 L，那么中间左半部分是 R 有右部分是 L，最中间（如果中间的 domino 个数是奇数的话）是 .
为了简化判断，可以在 domino 前放一个 L，后放一个 R。
- 只有相邻的受力 dominoes 才会相互影响
- 使用哨兵简化操作
- 语言支持：Python3
Python3 Code:
class Solution:
def pushDominoes(self, dominoes: str) -> str:
dominoes = 'L' + dominoes + 'R'
i = 0
j = i + 1
ans = ''
while j < len(dominoes):
if dominoes[j] == '.':
j += 1
continue
count = (j - i - 1)
if i != 0 :ans += dominoes[i]
if dominoes[i] == 'L' and dominoes[j] == 'R':
ans += '.' * count
elif dominoes[i] == 'L' and dominoes[j] == 'L':
ans += 'L' * count
elif dominoes[i] == 'R' and dominoes[j] == 'R':
ans += 'R' * count
elif dominoes[i] == 'R' and dominoes[j] == 'L':
ans += 'R' * (count//2) + '.'*(count%2) + 'L' * (count//2)
i = j
j += 1
return ans
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 8mo ago