亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。
亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。 (这个是力扣上面的题877)
示例:
输入:[5,3,4,5]
输出:true
解释:
亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗,这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。
这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true 。
题解:
解题思路
此处撰写解题思路
- 两种情况 亚历克斯可以从左边拿 ,也可以从右边 如果其中有一边结果true 亚历克斯就胜利(题目大意。我刚开始没看懂哈哈)
- 写一个公共函数 执行拿石头的操作。返回拿石头的结果。
- 然后 我们从左边拿一边 右边拿一边 。然后进行 || 就行了。很简单。
代码
class Solution {
/**
* @param Integer[] $stone 石头 Integer $isTake 0代表亚历克斯从左拿 反之从右
* @return Boolean
*/
function take($stone,$isTake){
$stoneCount = count($stone);
$alex = 0;//代表:亚历克斯
$li = 0;//代表:李
for ($i=0;$i<$stoneCount;$i++){
if($isTake == 0){
$alex += $stone[$i];
$isTake = 1;
}else{
$li += $stone[$i];
$isTake = 0;
}
}
return $alex > $li;
}
/**
* @param Integer[] $piles
* @return Boolean
*/
function stoneGame($piles) {
$piles =[3,7,2,3];
$isTake = 0;//0亚历克斯 拿 1 李 拿
$left = $this->take($piles,$isTake);//从左边拿
$isTake = 1;
$right = $this->take($piles,$isTake);//从右边拿
if($left || $right){//判断从左边拿或者从右边拿 的结果。如果有一个等于true 就返回true
return true;
}
return false;
}
}
下面是运行结果。感觉这种$piles 基数不大的情况下,测试不到真实算法实际情况。
原创文章,作者:星辰,如若转载,请注明出处:https://www.z88j.com/303.html