838. 推多米诺

题目链接

838. 推多米诺 - 力扣（LeetCode）

题目描述

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.."

解题思路

1. 问题描述：
   • 给定一个表示多米诺骨牌初始状态的字符串dominoes，其中'L'表示向左倒，'R'表示向右倒，'.'表示直立。
   • 当一个骨牌倒下时，它会推动相邻的骨牌朝相同方向倒下。
   • 要求模拟所有骨牌的最终状态。
2. 关键观察：
   • 两个相邻的'L'或'R'之间的所有'.'会被填充为相同的方向。
   • 如果一个'R'后面跟着一个'L'，则中间的'.'会从两边向中间倒下，直到相遇。
   • 边界情况可以通过添加哨兵字符（'L'和'R'）来简化处理。
3. 算法选择：
   • 使用双指针法，pre记录前一个非'.'字符的位置，i遍历当前字符。
   • 分三种情况处理：
     • s[i] == s[pre]：中间的'.'全部变为s[i]。
     • s[i] == 'L' && s[pre] == 'R'：中间的'.'从两边向中间倒下。
     • s[i] == 'R' && s[pre] == 'L'：中间的'.'不受影响。
   • 最后去掉哨兵字符，得到结果。

题解代码

classSolution{publicStringpushDominoes(Stringdominoes){// 在原始字符串前后添加哨兵字符 'L' 和 'R'，方便处理边界情况char[]s=("L"+dominoes+"R").toCharArray();intpre=0;// 记录前一个非 '.' 字符的位置（初始为哨兵 'L' 的位置）for(inti=1;i<s.length;i++){if(s[i]=='.'){continue;// 跳过当前点，继续检查下一个字符}// 情况1：当前字符与前一个非 '.' 字符相同（L...L 或 R...R）if(s[i]==s[pre]){// 将 pre 和 i 之间的所有 '.' 替换为 s[i]Arrays.fill(s,pre+1,i,s[i]);}// 情况2：当前字符是 'L' 且前一个非 '.' 字符是 'R'（R...L）elseif(s[i]=='L'){// 计算中间位置intmid=(pre+i)/2;// 如果 (pre + i) 是奇数，说明中间有一个 '.' 不需要改变// 前半部分（pre+1 到 mid）变为 'R'Arrays.fill(s,pre+1,mid+1,'R');// 后半部分（mid+1 到 i-1）变为 'L'Arrays.fill(s,mid+1,i,'L');}// 情况3：当前字符是 'R' 且前一个非 '.' 字符是 'L'（L...R）// 不需要处理，因为中间的 '.' 不受影响// 更新 pre 为当前非 '.' 字符的位置pre=i;}// 去掉首尾的哨兵字符，返回结果returnnewString(s,1,s.length-2);}}

复杂度分析

1. 时间复杂度：
   • 遍历字符串一次，时间复杂度为O(n)。
   • Arrays.fill操作在最坏情况下也是O(n)，但总体仍然是O(n)。
2. 空间复杂度：
   • 使用了一个字符数组s，大小为O(n)。
   • 其他变量为常数空间。
   • 总空间复杂度为O(n)。