Python 中修改后的字符串的最终状态

pythonserver side programmingprogramming更新于 2025/10/17 15:40:17

假设我们有一个字符串 S。长度为 n。这 n 个框彼此相邻，位置 i 处的字符 R 表示第 i 个框被推向右侧。类似地，位置 i 处的 L 表示第 i 个框被推向左侧，点 '.' 表示空白处。从初始配置开始，在每个时间单位，被推向右侧的框能够将下一个框推向右侧，左侧也可以应用相同的操作。当没有更多移动可行时，我们必须找到所有盒子的最终位置。

因此，如果输入为 R..R...L.，则输出将为 RRRRR.LL。

为了解决这个问题，我们将遵循以下步骤 −

N := 字符串大小
移动 := 大小为 N 的数组，用 0 填充
m := 0
对于 0 到 N 范围内的 i，执行
- 如果 string[i] 与 'R' 相同，则
  - m := N
- 否则，当 string[i] 与 'L' 相同时，则
  - m := 0
- 否则，
  - m := m - 1 中的最大值，0
- movement[i] := movement[i] + m
m := 0
对于范围 N - 1 到 -1 中的 i，减少 1，执行
- 如果 string[i] 与 'L' 相同，则
  - m := N
- 否则，当 string[i] 与 'R' 相同时，则
  - m := 0
- 否则，
  - m := m 的最大值 - 1, 0
- movement[i] := movement[i] - m
如果 m 为 0，则通过添加点来生成字符串，否则当 m > 0 时返回 'R'，否则对于 movement 中的每个元素 m，返回 'L'。

示例代码

让我们看看下面的实现以便更好地理解 −

def get_final_pos(string):
   N = len(string)
   movement = [0] * N
   m = 0
   for i in range(0, N):
      if string[i] == 'R':
         m = N
      elif string[i] == 'L':
         m = 0
      else:
         m = max(m - 1, 0)
      movement[i] += m
   m = 0
   for i in range(N - 1, -1, -1):
      if string[i] == 'L':
         m = N
      elif string[i] == 'R':
         m = 0
      else:
         m = max(m - 1, 0)
      movement[i] -= m
return "".join('.' if m == 0 else 'R' if m > 0 else 'L' for m in movement)
print(get_final_pos('R..R...L.'))