Chương trình để có được vị trí cuối cùng của động vật di chuyển khi chúng dừng lại bằng Python

Giả sử chúng ta có một chuỗi s đại diện cho các điều kiện ban đầu của một số động vật. Mỗi con vật có thể nhận một trong ba giá trị:L, cho biết con vật được di chuyển sang trái. R, cho biết con vật di chuyển sang phải. @, cho biết con vật đang đứng yên. Động vật di chuyển trên một hướng sẽ chọn động vật khác trừ khi động vật đó nhận được một lực từ hướng ngược lại. Sau đó, nó sẽ đứng yên. Chúng ta phải tìm ra hướng của mỗi con vật khi con vật đó ngừng di chuyển.

Vì vậy, nếu đầu vào là s =​​"@@ L @ R @@@@ L", thì đầu ra sẽ là "LLL @ RRRLLL"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Level:=một danh sách có kích thước giống như s và điền vào -1

• q:=một hàng đợi kết thúc kép

• cho idx nằm trong phạm vi từ 0 đến kích thước của s, thực hiện

  • nếu s [idx] giống "R" hoặc s [idx] giống "L" thì

    • insert (idx, 0, s [idx]) vào cuối q

• l:=một danh sách các ký tự mới của s

• trong khi q không trống, thực hiện

  • (idx, new_level, dir):=phần tử bên trái của q và xóa nó khỏi q

  • nếu các cấp [idx] giống -1 thì

    • các cấp [idx]:=new_level

    • l [idx]:=dir

    • nếu dir giống như "R" và idx + 1

      • insert (idx + 1, new_level + 1, dir) vào cuối q

    • ngược lại khi dir giống như "L" và idx - 1> =0, thì

      • insert (idx - 1, new_level + 1, dir) vào cuối q

  • ngược lại, khi các cấp [idx] giống với new_level thì

    • nếu l [idx] không giống với dir, thì

      • l [idx]:="@"

• trả về một chuỗi bằng cách nối các phần tử của l

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

LLL@RRRLLL