欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

硬币排成线 395.硬币排成线Ⅱ C++

程序员文章站 2022-04-12 21:48:20
394.硬币排成线Ⅰ 问题描述:有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定 第一个玩家 是输还...

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 getMax(len+1);和int getMax[len + 1];定义数组时都没毛病,但不知道为什么,不指定长度,这样的话vector getMax;就会报错,错误提示是这样的

输入

[1,2,2]
期望答案
true
错误信息

Segmentation fault (core dumped)