Chương trình biến đổi hai danh sách thành giống nhau bằng phép tổng dãy con bằng Python

Cho hai danh sách l1 và l2. Lặp lại phép toán: chọn một dãy con liên tiếp, thay thế toàn bộ dãy con bằng tổng của nó. Tìm độ dài lớn nhất có thể của danh sách kết quả sau khi làm cho hai danh sách giống nhau. Nếu không thể, trả về -1.

Ví dụ: l1 = [1,4,7,1,2,10], l2 = [5,6,1,3,10] → 4 (ghép thành [5,7,3,10]).

Quy trình giải quyết (Two Pointers từ cuối)

1. Khởi tạo i = len(l1)-1, j = len(l2)-1, res = 0.
2. Trong khi i >= 0 và j >= 0:
   • Nếu l1[i] == l2[j]: tăng res, giảm i, j.
   • Nếu l1[i] < l2[j]: gộp l1[i] vào l1[i-1] (nếu có), giảm i.
   • Nếu l1[i] > l2[j]: gộp l2[j] vào l2[j-1] (nếu có), giảm j.
3. Nếu cả i và j đều về -1, trả về res, ngược lại -1.

Ví dụ mã nguồn

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

Đầu vào

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

Đầu ra

4