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

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

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

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

  • N := 字符串的大小
  • movement := 大小为 N 的数组，填充为 0
  • m := 0
  • 对于 i 从 0 到 N 的范围，执行以下操作：
    • 如果 string[i] 与 'R' 相同，则
      • m := N
    • 否则，如果 string[i] 与 'L' 相同，则
      • m := 0
    • 否则，
      • m := m - 1 和 0 的最大值
    • movement[i] := movement[i] + m
  • m := 0
  • 对于 i 从 N - 1 到 -1 的范围，递减 1，执行以下操作：
    • 如果 string[i] 与 'L' 相同，则
      • m := N
    • 否则，如果 string[i] 与 'R' 相同，则
      • m := 0
    • 否则，
      • m := m - 1 和 0 的最大值
    • movement[i] := movement[i] - m
  • 返回通过添加点（如果 m 为 0）或 'R'（如果 m > 0），否则为每个元素 m 在 movement 中添加 '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.'))

输入

'R..R...L.'

输出

RRRRR.LL.

更新于: 2020年8月28日

106 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告