โปรแกรมนับจำนวนการสลับที่ต้องใช้เพื่อเปลี่ยนลิสต์หนึ่งเป็นอีกลิสต์ใน Python

สมมติว่าเรามีสองลิสต์ L1 และ L2 ความยาวเท่ากัน n ค่าแต่ละตัวไม่ซ้ำกัน และอยู่ในช่วง 1 ถึง n หาจำนวนการสลับติดกัน (adjacent swaps) น้อยที่สุดเพื่อเปลี่ยน L1 ให้กลายเป็น L2

ตัวอย่าง

อินพุต: L1 = [0, 1, 2, 3], L2 = [2, 0, 1, 3]

เอาต์พุต: 2

สลับ 1 กับ 2 -> [0, 2, 1, 3] แล้วสลับ 0 กับ 2 -> [2, 0, 1, 3]

ขั้นตอนการแก้ปัญหา

จับคู่ตำแหน่งใน L1 ตามลำดับใน L2:

1. ans = 0
2. สำหรับแต่ละ req ใน L2:
   • หาดัชนี i ของ req ใน L1
   • ลบอิลิเมนต์ตำแหน่ง i ออกจาก L1
   • ans += i (จำนวนการสลับที่ต้องย้ายมาหน้า)
3. คืนค่า ans

การนำไปใช้ใน Python

class Solution:
    def solve(self, L1, L2):
        ans = 0
        for req in L2:
            i = L1.index(req)
            L1.pop(i)
            ans += i
        return ans

ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))

อินพุต

[0, 1, 2, 3], [2, 0, 1, 3]

เอาต์พุต

2