โปรแกรมแปลงรายการหนึ่งเหมือนกับรายการอื่นด้วยการดำเนินการรวมรายการย่อยใน Python

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

ดังนั้น หากอินพุตเป็น l1 =[1, 4, 7, 1, 2, 10] l2 =[5, 6, 1, 3, 10] ผลลัพธ์จะเป็น 4 ราวกับว่าเราดำเนินการดังนี้ ดังต่อไปนี้ -

• ใช้รายการย่อยของ l1 [1, 4] เราได้ [5, 7, 1, 2, 10]
• เอารายการย่อยของ l1 [1, 2] เราได้รับ [5, 7, 3, 10]
• เอารายการย่อยของ l2 [6, 1] เราได้รับ [5, 7, 3, 10].

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

• i :=ขนาดของ l1 - 1, j :=ขนาดของ l2 - 1, res :=0
• ในขณะที่ i>=0 และ j>=0 ทำ
  • ถ้า l1[i] เหมือนกับ l2[j] แล้ว
    • res :=res + 1, i :=i - 1, j :=j - 1
  • มิฉะนั้นเมื่อ l1[i]
  • ถ้า i> 0 ไม่ใช่ศูนย์ ดังนั้น
    • l1[i - 1] :=l1[i - 1] + l1[i]
  • i :=i - 1
• มิฉะนั้นเมื่อ l1[i]> l2[j] แล้ว
  • ถ้า j> 0 แล้ว
    • l2[j - 1] :=l2[j - 1] + l2[j]
  • j :=j - 1

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

4