硬币排成线 395.硬币排成线Ⅱ C++
394.硬币排成线Ⅰ
问题描述：有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定 第一个玩家 是输还是赢？
样例：n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
n = 4, 返回 true.
n = 5, 返回 true.
挑战：O(1) 时间复杂度且O(1) 存储。
分析：只有1、2枚硬币时，第一个人稳赢，因为第二个人没得拿；有3枚硬币时，第一个人无论拿一个还是两个都是必输的；当有4枚硬币时，只要第一个人先拿1枚硬币，就可以稳赢；当然5枚硬币时，只要第一次拿2枚硬币就稳赢，可以看出只要硬币数是3的倍数，那么第一名玩家是必输的，原因很简单，博弈论不存在谁聪明谁笨蛋的情况，那么只有是3的倍数时，当第一个玩家拿1个硬币，第二个玩家拿2个硬币，当第一个玩家拿2个硬币，第二个玩家拿1个硬币，这样第二个玩家便能保证3的倍数个硬币，最后一次拿硬币的一定是自己，这种情况第一个玩家是必输的，没错，就是这样。好吧，第一次用自然语言描述有关博弈论的问题，其实我是找规律找出来的，哈哈，不要笑我......
class Solution {
public:
/*
* @param n: An integer
* @return: A boolean which equals to true if the first player will win
*/
bool firstWillWin(int n) {
// write your code here
if( n % 3 == 0){
return false;
}else{
return true;
}
}
};
395.硬币排成线Ⅱ
问题描述：有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。
请判定 第一个玩家是输还是赢？
样例：
给定数组 A = [1,2,2], 返回 true.
给定数组 A = [1,2,4], 返回 false.
分析：首先，如果硬币只有1、2个的话，即len <= 2时，那么第一个人全部拿走，稳赢；然后其他情况我们分析，用数组getMax[i]来表示从i到最后第一个人能拿到的最大值，具体数组里元素的取值分析可参考大牛的分析，给数组getMax赋完值之后，那么getMax[0]即为第一个人能够拿到的最大值，然后循环求出所有硬币之和sum，求出第二个人能够拿到的最大值，比较两者大小，就可以判断出第一个玩家的输赢了。呼...终于完了，然而重点分析都不是我写了，嘿嘿...
class Solution {
public:
/*
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
bool firstWillWin(vector &values) {
// write your code here
int len = values.size();
// vector getMax(len+1);
int getMax[len + 1];
if(len <= 2){
return true;
}
getMax[len] = 0;
getMax[len - 1] = values[len - 1];
getMax[len - 2] = values[len - 1] + values[len - 2];
getMax[len - 3] = values[len - 2] + values[len - 3];
for(int i = len - 4;i >= 0;i--){
int getMax1 = values[i] + (getMax[i+2] < getMax[i+3] ? getMax[i+2] : getMax[i+3]);
int getMax2 = values[i] + values[i+1] + (getMax[i+3] < getMax[i+4] ? getMax[i+3] : getMax[i+4]);
getMax[i] = getMax1 > getMax2 ? getMax1 : getMax2;
}
int sum = 0;
for(int a = 0;a < len;a++){
sum += values[a];
}
if(getMax[0] > (sum - getMax[0])){
return true;
}else{
return false;
}
}
};
好了，最后，本文参考了Vector类和数组的区别，有需要的也可以看看，大神总结的很清晰，不过，个人觉得，如果不是需要经常做删除添加操作的话，定长的话，还是数组比较好！另外上述代码用vector
输入
[1,2,2]
期望答案
true
错误信息 Segmentation fault (core dumped)