20250502 LeetCode每日一题——838. 推多米诺

838. 推多米诺

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 <= 10<sup>5</sup>
dominoes[i] 为 'L'、'R' 或 '.'

题解

个人使用双指针思路，思路没有官方的实现方式巧妙，但也算是笨人有笨方法。刚开始刷LeetCode，代码写的比较丑陋。具体的思路就是，一个指针指向字符串开头，根据该字符和下一个字符的内容，决定结果。两个指针分别是 left和 right，对应的字符就用其代替，初始时 left=0 ，right=1：

如果 left=.，那么向右移动 right，如果：
- right=L，那么将 left到 right中的所有字符都变成 L；
- right=.，那么将 right继续向右移动，若 right移动到结束，则将所有 .维持不变；
- right=R，将 left到 right之间的所有符号变成 .；
- 做完上述操作后，将 left移动到 right的位置。
如果 left=R，那么向右移动 right，如果：
- right=L，那么将 left到 right之间的 .字符对称分割为 R和 L；
- right=.，那么将 right继续向右移动，如果 right移动到结束，则将所有 R更改为 .；
- right=R，将 left到 right之间的所有符号变成 R ；
- 做完上述操作后，将 left移动到 right的位置。
如果 left=L，那么直接向右移动 left；

经过上述思路的代码实现如下：

# -*- coding: utf-8 -*-

# 双指针，遇到 . 则等待下一个L，如果途中遇到R，则直接跳转到R，不再等待；
# 遇到L，则直接跳到L，不再等待
# 遇到R，则等待下一个L，R和L对半分，直到到达中间

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        left = 0
        right = 0
        ret = ''
        while left < len(dominoes) and right < len(dominoes):
            if left == len(dominoes) - 1:
                ret += dominoes[left]
                break
            right = left + 1
            if dominoes[left] == '.':
                while right < len(dominoes):
                    if dominoes[right] == 'L':
                        ret += 'L' * (right - left + 1)
                        left = right + 1
                        # right = left
                        break
                    elif dominoes[right] == 'R':
                        ret += '.' * (right - left)
                        left = right
                        # ret += 'R'
                        break
                    elif dominoes[right] == '.':
                        right += 1
                        if right >= len(dominoes):
                            ret += '.' * (right - left)
            elif dominoes[left] == 'L':
                ret += 'L'
                left += 1
                # right = left
            else:
                while right < len(dominoes):
                    if dominoes[right] == 'R':
                        ret += 'R' * (right - left)
                        left = right
                        # right = left
                        break
                    elif dominoes[right] == '.':
                        right += 1
                        if right >= len(dominoes):
                            ret += 'R' * (right - left)
                    else:
                        interval = right - left + 1
                        if interval % 2 == 0:
                            ret = ret + 'R' * (interval // 2) + 'L' * (interval // 2)
                        else:
                            ret = ret + 'R' * (interval // 2) + '.' + 'L' * (interval // 2)
                        left = right + 1
                        # right = left
                        break
        return ret


if __name__ == '__main__':
    s = Solution()
    print(s.pushDominoes(".R..L."))

提交记录

https://leetcode.cn/problems/push-dominoes/submissions/626959701/