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] < l2[j] 時，則
    • 如果 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
• 如果 i 等於 -1 且 j 等於 -1，則返回 res，否則返回 -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

Arnab Chakraborty

更新於： 2020年10月19日

105 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習