โปรแกรมทำให้สองลิสต์เหมือนกันด้วยการแทนซับลิสต์ด้วยผลรวมใน Python

สมมติว่าเรามีสองลิสต์ l1 และ l2 ต้องทำให้ลิสต์เท่ากันโดยดำเนินการซ้ำ: เลือกซับลิสต์ แทนที่ด้วยผลรวมของมัน หาความยาวสูงสุดของลิสต์ผลลัพธ์ ถ้าไม่มีคำตอบ คืนค่า -1

ตัวอย่าง: l1 = [1, 4, 7, 1, 2, 10], l2 = [5, 6, 1, 3, 10] ผลลัพธ์ 4

ขั้นตอนการแก้ปัญหา (Two Pointers จากท้าย)

1. i = len(l1)-1, j = len(l2)-1, res = 0
2. วนลูป while i >= 0 และ j >= 0:
   • ถ้า l1[i] == l2[j]: res += 1, i -= 1, j -= 1
   • ถ้า l1[i] < l2[j]:
     • ถ้า i > 0: l1[i-1] += l1[i]
     • i -= 1
   • ถ้า l1[i] > l2[j]:
     • ถ้า j > 0: l2[j-1] += l2[j]
     • j -= 1
3. คืนค่า res ถ้า i == -1 and j == -1 มิฉะนั้น -1

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

class Solution:
    def solve(self, l1, l2):
        i, j, res = len(l1) - 1, len(l2) - 1, 0
        while i >= 0 and j >= 0:
            if l1[i] == l2[j]:
                res, i, j = res + 1, i - 1, j - 1
            elif l1[i] < l2[j]:
                if i > 0:
                    l1[i - 1] += l1[i]
                i -= 1
            elif l1[i] > l2[j]:
                if j > 0:
                    l2[j - 1] += l2[j]
                j -= 1
        return res if i == -1 and j == -1 else -1

ob = Solution()
l1 = [1, 4, 7, 1, 2, 10]
l2 = [5, 6, 1, 3, 10]
print(ob.solve(l1, l2))  # Output: 4

อินพุต / เอาต์พุต

Input: [1, 4, 7, 1, 2, 10], [5, 6, 1, 3, 10]

Output: 4