Python程式：透過給定操作減少列表並找到剩餘的最小數字

假設我們有一個名為nums的正數列表。現在考慮一個操作，我們從中移除任意兩個值a和b，其中a ≤ b，如果a < b有效，則將b-a插入回列表nums中。如果我們可以執行任意數量的操作，我們必須找到可以得到的最小剩餘數字。如果列表為空，則返回0。

因此，如果輸入類似於nums = [2, 4, 5]，則輸出將為1，因為我們可以選擇4和5，然後插入1以得到[2, 1]。現在選擇2和1以得到[1]。

為了解決這個問題，我們將遵循以下步驟：

• s := nums中所有元素的總和
• 定義一個函式f()。它將接收i和s作為引數。
• 如果i ≥ nums的大小，則
  • 返回s
• n := nums[i]
• 如果s - 2 * n < 0，則
  • 返回f(i + 1, s)
• 返回f(i + 1, s - 2 * n)和f(i + 1, s)的最小值
• 在主方法中返回f(0, s)

示例

讓我們看看下面的實現來更好地理解：

def solve(nums):
   s = sum(nums)

   def f(i, s):
      if i >= len(nums):
         return s
      n = nums[i]
      if s - 2 * n < 0:
         return f(i + 1, s)
      return min(f(i + 1, s - 2 * n), f(i + 1, s))

   return f(0, s)

nums = [2, 4, 5]
print(solve(nums))

輸入

[2, 4, 5]

輸出

1

Arnab Chakraborty

更新於：2021年10月18日

233 次瀏覽

開啟你的職業生涯

完成課程後獲得認證

開始學習