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

解题思路

这道题需要模拟多米诺骨牌的倒塌过程。关键在于理解不同区间的处理规律：

核心思路：

  1. 使用双指针找到所有的"力区间"，即相邻两个非’.‘字符之间的区间
  2. 对每种区间类型进行分类处理：
    • R...R 或 L...L：整个区间都倒向同一方向
    • R...L：两端向中间倒，中间可能有平衡点
    • L...R：两个力互不影响，中间保持直立
  3. 边界情况：字符串开头和结尾的处理

算法步骤：

  1. 在字符串首尾添加虚拟字符’L’和’R’便于统一处理
  2. 用双指针遍历，找到每一段连续的区间
  3. 根据区间两端的字符类型决定中间部分的最终状态：
    • L...L：全部变为’L’
    • R...R：全部变为’R'
    • R...L：从两端向中间倒，距离相等时保持’.'
    • L...R：中间部分保持不变

时间复杂度O(n)，空间复杂度O(1)（除了结果数组）。这种方法避免了模拟每一秒的过程，直接计算最终状态。

代码实现

class Solution {
public:
    string pushDominoes(string dominoes) {
        string s = "L" + dominoes + "R";
        string result = dominoes;
        
        for (int i = 0, j = 1; j < s.length(); j++) {
            if (s[j] == '.') continue;
            
            if (s[i] == s[j]) {
                // 同向力，整个区间都倒向该方向
                for (int k = i + 1; k < j; k++) {
                    result[k - 1] = s[i];
                }
            } else if (s[i] == 'R' && s[j] == 'L') {
                // 相对的力，从两端向中间倒
                for (int k = i + 1, l = j - 1; k <= l; k++, l--) {
                    if (k == l) break; // 中间位置保持不变
                    result[k - 1] = 'R';
                    result[l - 1] = 'L';
                }
            }
            // L...R的情况中间保持不变，无需处理
            
            i = j;
        }
        
        return result;
    }
};

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        s = 'L' + dominoes + 'R'
        result = list(dominoes)
        
        i = 0
        for j in range(1, len(s)):
            if s[j] == '.':
                continue
                
            if s[i] == s[j]:
                # 同向力，整个区间都倒向该方向
                for k in range(i + 1, j):
                    result[k - 1] = s[i]
            elif s[i] == 'R' and s[j] == 'L':
                # 相对的力，从两端向中间倒
                left, right = i + 1, j - 1
                while left <= right:
                    if left == right:
                        break  # 中间位置保持不变
                    result[left - 1] = 'R'
                    result[right - 1] = 'L'
                    left += 1
                    right -= 1
            # L...R的情况中间保持不变，无需处理
            
            i = j
            
        return ''.join(result)

public class Solution {
    public string PushDominoes(string dominoes) {
        string s = "L" + dominoes + "R";
        char[] result = dominoes.ToCharArray();
        
        for (int i = 0, j = 1; j < s.Length; j++) {
            if (s[j] == '.') continue;
            
            if (s[i] == s[j]) {
                // 同向力，整个区间都倒向该方向
                for (int k = i + 1; k < j; k++) {
                    result[k - 1] = s[i];
                }
            } else if (s[i] == 'R' && s[j] == 'L') {
                // 相对的力，从两端向中间倒
                for (int k = i + 1, l = j - 1; k <= l; k++, l--) {
                    if (k == l) break; // 中间位置保持不变
                    result[k - 1] = 'R';
                    result[l - 1] = 'L';
                }
            }
            // L...R的情况中间保持不变，无需处理
            
            i = j;
        }
        
        return new string(result);
    }
}

var pushDominoes = function(dominoes) {
    const s = 'L' + dominoes + 'R';
    const result = dominoes.split('');
    
    for (let i = 0, j = 1; j < s.length; j++) {
        if (s[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每个字符最多被处理常数次
空间复杂度O(1)除了结果数组外，只使用常数额外空间