877. 石子游戏

题目如下:

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。

亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。

因为共偶数堆且总和为奇数,比如共 M 堆,从 1,2,3...,M,那么奇数堆之和和偶数堆之和肯定有一个更大的,只要刚开始我们能够计算好到底是那一个的总和更大,我们就可以按照想要的结果来进行挑选了,这是先手的那个人可以控制的。

【思路】

  • 题目的意思就是,把N个石头摆成M堆,其中N是奇数,M是偶数
  • 我们把石头的堆数编号,1,2,3,4,...,M,令奇数堆的石头总和为A,偶数堆的石头总和为B
  • 那么要么A>B,要么B>A
  • 所以,先取的玩家,只要自己先判断一下场上是A>B还是B>A就能必胜。必胜策略如下:
    • 若A>B,即奇数堆的石头总和>偶数堆的石头总和,先手的玩家就取奇数堆。先取第一堆石头,那么后手的玩家只能取偶数堆的石头了
    • 若A<B,即偶数堆的石头总和>奇数堆的石头总和,先手的玩家就取偶数堆。先取最后一堆石头,那么后手的玩家只能取奇数堆的石头了
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 题目 (https://leetcode-cn.com/problems/stone-game/)亚历克斯和李用几...
    Mastergad阅读 1,715评论 0 0
  • 题目描述 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。 游戏以谁...
    zhipingChen阅读 3,226评论 2 1
  • 题目链接难度: 中等 类型:动态规划 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都...
    wzNote阅读 12,252评论 0 1
  • 1、题目 877. 石子游戏 2、题解 首先,一开始我觉得这道题目并不严谨。因为我大略感觉到先手选择的人就能赢得这...
    风卷晨沙阅读 1,634评论 0 0
  • 我一生下来就成了爸爸妈妈的小宝贝,小时一直是父母照顾我。但现在,我觉得我长大了,能照顾他们了。 九岁那...
    枫珈阅读 5,206评论 0 0

友情链接更多精彩内容