Python程序：获取移动动物停止时的最终位置

假设我们有一个字符串s，它表示一些动物的初始状态。每只动物可以取三个值之一：L，表示动物向左移动；R，表示动物向右移动；@，表示动物静止不动。沿某个方向移动的动物会拾起其他动物，除非该动物受到来自相反方向的力，否则它将静止不动。我们必须找到每只动物停止移动时的方向。

因此，如果输入类似于s = "@@L@R@@@@L"，则输出将是"LLL@RRRLLL"

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

  • levels := 一个大小与s相同的列表，并填充-1

  • q := 一个双端队列

  • 对于索引idx从0到s的大小，执行：

    • 如果s[idx]与"R"或s[idx]与"L"相同，则

      • 将(idx, 0, s[idx])插入q的末尾

  • l := 一个新的s字符列表

  • 当q不为空时，执行：

    • (idx, new_level, dir) := q的左元素，并将其从q中删除

    • 如果levels[idx]与-1相同，则

      • levels[idx] := new_level

      • l[idx] := dir

      • 如果dir与"R"相同且idx + 1 < l的大小，则

        • 将(idx + 1, new_level + 1, dir)插入q的末尾

      • 否则，如果dir与"L"相同且idx - 1 >= 0，则

        • 将(idx - 1, new_level + 1, dir)插入q的末尾

    • 否则，如果levels[idx]与new_level相同，则

      • 如果l[idx]与dir不同，则

        • l[idx] := "@"

  • 返回通过连接l的元素组成的字符串

示例

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

 在线演示

from collections import deque
class Solution:
   def solve(self, s):
      levels = [-1 for i in s]
      q = deque()
      for idx in range(len(s)):
         if s[idx] == "R" or s[idx] == "L":
            q.append((idx, 0, s[idx]))
      l = list(s)
      while q:
         idx, new_level, dir = q.popleft()
         if levels[idx] == -1:
            levels[idx] = new_level
            l[idx] = dir
            if dir == "R" and idx + 1 < len(l):
               q.append((idx + 1, new_level + 1, dir))
            elif dir == "L" and idx - 1 >= 0:
               q.append((idx - 1, new_level + 1, dir))
         elif levels[idx] == new_level:
            if l[idx] != dir:
               l[idx] = "@"
      return "".join(l)
ob = Solution()
s = "@@L@R@@@@L"
print(ob.solve(s))

输入

"@@L@R@@@@L"

输出

LLL@RRRLLL

更新于：2020年12月22日

浏览量：136

开启您的职业生涯

完成课程后获得认证

开始
广告
© . All rights reserved.