Chương trình chuyển đổi một danh sách giống hệt danh sách khác với hoạt động tính tổng danh sách con bằng Python

Giả sử chúng ta có hai danh sách l1 và l2, chúng ta phải làm cho các danh sách bằng nhau bằng cách áp dụng thao tác này nhiều lần - Chọn một danh sách con và thay thế toàn bộ danh sách con bằng tổng của nó. Cuối cùng trả về kích thước của danh sách kết quả dài nhất có thể sau khi áp dụng các thao tác trên. Nếu không có giải pháp, hãy trả về -1.

Vì vậy, nếu đầu vào là l1 =[1, 4, 7, 1, 2, 10] l2 =[5, 6, 1, 3, 10], thì đầu ra sẽ là 4, như thể chúng ta thực hiện thao tác này như sau -

• Lấy danh sách phụ của l1 [1, 4], chúng tôi nhận được [5, 7, 1, 2, 10]
• Lấy danh sách phụ của l1 [1, 2], chúng tôi nhận được [5, 7, 3, 10]
• Lấy danh sách phụ của l2 [6, 1], chúng tôi nhận được [5, 7, 3, 10].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• i:=kích thước của l1 - 1, j:=kích thước của l2 - 1, res:=0
• while i> =0 and j> =0, do
  • nếu l1 [i] giống với l2 [j], thì
    • res:=res + 1, i:=i - 1, j:=j - 1
  • ngược lại khi l1 [i]
  • nếu i> 0 khác 0 thì
    • l1 [i - 1]:=l1 [i - 1] + l1 [i]
  • i:=i - 1
• ngược lại khi l1 [i]> l2 [j] thì
  • nếu j> 0, thì
    • l2 [j - 1]:=l2 [j - 1] + l2 [j]
  • j:=j - 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

4