Python程式：檢查第一個玩家能否獲得更多糖果

假設我們有一個名為candies的數字列表，兩個人正在爭奪收集最多糖果。比賽是輪流進行的，第一個人先開始，每一輪他可以從前面或後面拾取糖果。我們必須檢查第一個人是否能夠比其他人收集更多糖果。

因此，如果輸入類似於 candies = [1, 4, 3, 8]，則輸出為 True，因為第一個人可以在第一輪獲得 8 個糖果，而無論第二個人選擇 1 還是 3，第一個人都可以透過拿走任何剩餘的糖果獲勝。

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

  • N := candies 的大小

  • 定義一個函式 difference()。這將採用 left，right

  • 如果 left 等於 right，則

    • 返回 candies[left]

  • 返回 (candies[left] − difference(left + 1, right)) 和 (candies[right] − difference(left, right − 1)) 的最大值

  • 從主方法執行以下操作：

  • 當 difference(0, N − 1) > 0 時返回 true，否則返回 false

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

示例

 線上演示

class Solution:
   def solve(self, candies):
      N = len(candies)
      def difference(left, right):
         nonlocal candies
         if left == right:
            return candies[left]
         return max(candies[left] − difference(left + 1, right), candies[right] − difference(left, right − 1))
      return difference(0, N − 1) > 0
ob = Solution()
candies = [1, 4, 3, 8]
print(ob.solve(candies))

輸入

[1, 4, 3, 8]

輸出

True

更新於：2020年12月26日

瀏覽量：117

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告