โปรแกรมรับตำแหน่งสุดท้ายของสัตว์ที่เคลื่อนไหวเมื่อหยุดใน Python

สมมติว่าเรามีสตริงที่แสดงถึงเงื่อนไขเริ่มต้นของสัตว์บางชนิด สัตว์แต่ละตัวสามารถรับค่าใดค่าหนึ่งจากสามค่า:L หมายถึงสัตว์ที่ย้ายไปทางซ้าย R แสดงว่าสัตว์เคลื่อนไปทางขวา @ แสดงว่าสัตว์ยืนนิ่ง สัตว์ที่เคลื่อนที่ไปในทิศทางจะจับสัตว์อื่นเว้นแต่สัตว์จะได้รับแรงจากทิศทางตรงกันข้าม จากนั้นมันก็จะยืนนิ่ง เราต้องหาทิศทางของสัตว์แต่ละตัวเมื่อสัตว์หยุดเคลื่อนไหว

ดังนั้น หากอินพุตเป็น s ="@@L@R@@@@L" ผลลัพธ์จะเป็น "LLL@RRRLLL"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ระดับ :=รายการขนาดเท่ากับ 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

  • ถ้าระดับ[idx] เหมือนกับ -1 แล้ว

    • ระดับ[idx] :=new_level

    • ล[idx] :=dir

    • ถ้า dir เหมือนกับ "R" และ idx + 1

      • แทรก (idx + 1, new_level + 1, dir) ที่ส่วนท้ายของ q

    • มิฉะนั้นเมื่อ dir เหมือนกับ "L" และ idx - 1>=0 แล้ว

      • แทรก (idx - 1, new_level + 1, dir) ที่ส่วนท้ายของ q

  • มิฉะนั้นเมื่อระดับ[idx] เหมือนกับ new_level แล้ว

    • ถ้า l[idx] ไม่เหมือนกับ dir แล้ว

      • ล[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