สถานะสุดท้ายของสตริงหลังจากแก้ไขใน Python

สมมติว่าเรามีสตริง S ความยาวเท่ากับ n กล่อง n เหล่านี้ที่อยู่ติดกัน อักขระ R ที่ตำแหน่ง i แสดงว่ากล่องที่ i ถูกผลักไปทางขวา ในทำนองเดียวกัน L ที่ตำแหน่ง i แสดงว่ากล่องที่ i ถูกผลักไปทางซ้าย จุด '.' บ่งบอกถึงพื้นที่ว่าง เริ่มจากการกำหนดค่าเริ่มต้น ทุกครั้งที่หน่วย กล่องที่ถูกผลักไปทางด้านขวาสามารถผลักกล่องถัดไปไปทางขวา การกระทำเดียวกันสามารถนำไปใช้กับด้านซ้ายได้เช่นกัน เราต้องหาตำแหน่งสุดท้ายของกล่องทั้งหมดเมื่อไม่มีการเคลื่อนไหวอีกต่อไป

ดังนั้น หากอินพุตเป็น R..R...L. เอาต์พุตจะเป็น RRRRR.LL.

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

• N :=ขนาดของสตริง
• การเคลื่อนไหว :=อาร์เรย์ขนาด N เติม 0s
• ม :=0
• สำหรับผมในช่วง 0 ถึง N ให้ทำ
  • ถ้า string[i] เหมือนกับ 'R' แล้ว
    • ม :=ไม่มี
  • มิฉะนั้นเมื่อ string[i] เหมือนกับ 'L' แล้ว
    • ม :=0
  • มิฉะนั้น
    • m :=สูงสุด m - 1, 0
  • การเคลื่อนไหว[i] :=การเคลื่อนไหว[i] + m
• ม :=0
• สำหรับ i ในช่วง N - 1 ถึง -1, ลดลง 1, ทำ
  • ถ้า string[i] เหมือนกับ 'L' แล้ว
    • ม :=ไม่มี
  • มิฉะนั้นเมื่อ string[i] เหมือนกับ 'R' แล้ว
    • ม :=0
  • มิฉะนั้น
    • m :=สูงสุด m - 1, 0
  • การเคลื่อนไหว[i] :=การเคลื่อนไหว[i] - ม
• คืนค่าสตริงโดยเพิ่มจุดถ้า m เป็น 0 มิฉะนั้น 'R' เมื่อ m> 0 มิฉะนั้น 'L' สำหรับทุกองค์ประกอบ m ที่กำลังเคลื่อนที่

โค้ดตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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.