推多米诺

标签: 双指针 字符串 动态规划

难度: Medium

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

  • dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
  • dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
  • dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。

返回表示最终状态的字符串。

 

示例 1：

输入：dominoes = "RR.L"
输出："RR.L"
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：

输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

提示：

  • n == dominoes.length
  • 1 <= n <= 105
  • dominoes[i] 为 'L'、'R' 或 '.'

Submission

运行时间: 100 ms

内存: 17.4 MB

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        ds = list(dominoes)
        n = len(dominoes)
        i, left = 0, 'L'
        while i < n:
            j = i
            while j < n and ds[j] == '.':
                j += 1
            right = ds[j] if j < n else 'R'
            if left == right:
                while i < j:
                    ds[i] = right
                    i += 1
            elif left == 'R' and right == 'L':
                k = j - 1
                while i < k:
                    ds[i] = 'R'
                    ds[k] = 'L'
                    i += 1
                    k -= 1
            left = right
            i = j + 1
        return ''.join(ds)

Explain

该题解主要通过模拟多米诺骨牌倒下的过程来解决问题。首先，将输入字符串转换为列表以便修改。接着，使用两个指针i和j来遍历列表，i是当前考虑的起始位置，j用于寻找连续的'.'的结束位置。变量left表示当前段落的左边界状态（即前一个非'.'的字符），right表示当前段落的右边界状态（即第一个非'.'的字符）。根据left和right的不同组合，有以下几种情况：1)如果两边字符相同（'L'或'R'），则将中间的'.'全部改为该字符；2)如果左边是'R'，右边是'L'，则从两边向中间推进，直到两指针相遇或交叉，分别设置为'R'和'L'；3)如果左右边界不形成推动力（如'.'或相对的'L'和'R'），则保持中间的'.'不变。在处理完所有段落后，将列表转换回字符串形式作为结果。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义解决方案类
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        # 将字符串转为列表以便修改
        ds = list(dominoes)
        n = len(dominoes)
        i, left = 0, 'L'  # 初始化指针和左边界
        while i < n:  # 遍历所有字符
            j = i
            # 寻找连续的'.'的结束位置
            while j < n and ds[j] == '.':
                j += 1
            # 确定右边界
            right = ds[j] if j < n else 'R'
            # 根据左右边界确定中间部分的倒向
            if left == right:
                while i < j:
                    ds[i] = right
                    i += 1
            elif left == 'R' and right == 'L':
                k = j - 1
                while i < k:
                    ds[i] = 'R'
                    ds[k] = 'L'
                    i += 1
                    k -= 1
            # 更新左边界为当前右边界，并移动i到下一个位置
            left = right
            i = j + 1
        # 将列表转换回字符串并返回
        return ''.join(ds)

Explore

是的，这种情况已经被考虑在内。当左右边界字符相同时，不论是'L'或'R'，中间的所有'.'都会改为与边界相同的字符。例如在'R.....'这种情况下，如果遇到右边界也是'R'（或者没有一个明确的右边界，即到达字符串末尾），所有的'.'都会被转换为'R'。这确保了多米诺的倒向与其相邻的推力方向一致。

选择从两边向中间填充是为了模拟真实情况下多米诺骨牌受到相对方向推力的影响。当左边界是'R'，右边界是'L'时，两边的力会相互作用，中间的点会受到左右两边的影响。从两边向中间填充'R'和'L'可以准确地模拟这种相互作用。当两指针相遇或交叉时，这表示中间的点已经完全被左右两边的力量平衡填充，确保了模拟的准确性。这种方法能有效处理任意长度的点段，确保每个点都得到正确的处理。

在字符串的开头和结尾是'.'的情况下，这些'.'的最终状态将由其相邻的非'.'字符决定。如果开头的'.'没有左边界（即开头即是'.'），则这些'.'不会被任何力量推动，因此保持为'.'。同理，如果结尾的'.'没有右边界（即结尾即是'.'），这些'.'也同样保持不变。如果某一段'.'的一侧被'R'或'L'界定，那么这些'.'将会转变为相邻的字符。这样的处理确保了边界情况也能得到合理的模拟。