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

开启你的职业生涯

完成课程获得认证

开始学习
广告