LeetCode 838. 推多米诺

Question

一行中有 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)$