Python程式：查詢可以使用硬幣湊成的最大連續值數量

假設我們有一個名為coins的陣列，包含n個元素，它表示我們擁有的硬幣。第i個硬幣的值表示為coins[i]。如果我們可以選擇一些硬幣，使得它們的值之和等於x，那麼我們就可以湊成值x。我們必須找到從0開始（包括0）可以獲得的最大連續值的數量。

因此，如果輸入類似coins = [1,1,3,4]，則輸出將為10，因為

  • 0 = []

  • 1 = [1]

  • 2 = [1,1]

  • 3 = [3]

  • 4 = [4]

  • 5 = [4,1]

  • 6 = [4,1,1]

  • 7 = [4,3]

  • 8 = [4,3,1]

  • 9 = [4,3,1,1]

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

  • 對列表coins進行排序

  • ans := 1

  • 對於coins中的每個硬幣，執行以下操作：

    • 如果coin > ans，則

      • 退出迴圈

    • ans := ans + coin

  • 返回ans

示例

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

def solve(coins):
   coins.sort()
   ans = 1
   for coin in coins:
      if coin > ans:
         break
      ans+=coin
   return ans

coins = [1,1,3,4]
print(solve(coins))

輸入

[1,1,3,4]

輸出

10

更新於: 2021年10月7日

385 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告