464、我能赢吗

leetcode

Created At : 2020-07-26 00:19

Count:1.4k Views 👀 :

Comment:

464、我能赢吗
1. 示例：

题解

1、记忆化递归
2、打表+找规律

464、我能赢吗

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

示例：

输入：
maxChoosableInteger = 10
desiredTotal = 11

输出：
false

解释：

无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

链接：https://leetcode-cn.com/problems/can-i-win

题解

通过一种累加策略，使得每两次累加都不能达到目标值，而且第n+1次累加可以达到目标值。

1、记忆化递归

代码

// C++
class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger == 0) {
            return true;
        }
        
        // 当谁也不能在最后取胜时，返回false，出题者最好能在题目注明下!
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
            return false;
        }

        // 用set维护可以选的数字，主要是因为set在删除和插入时比vector高效的多！
        set<int> mySet;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            mySet.insert(i);
        }

        // 用两个map维护备忘录
        // myMap1维护必赢的情况，myMap2维护必输的情况。
        map<int, int> myMap1, myMap2;          

        return dfs(mySet, 0, desiredTotal, myMap1, myMap2);                
    }
private:
    bool dfs(set<int>& mySet, int sum, int desiredTotal, map<int, int>& myMap1, map<int, int>& myMap2) {
        vector<int> nums;

        // 用了一个技巧，因为maxChoosableInteger不超过20，
        // 可以用一个int作为key来表示剩余数字的所有情况，每一个Bit代表对应的数字在set中。
        int key = 0;
        for (auto it : mySet) {
            nums.push_back(it);
            key |= (1 << it);
        }

        // 在必赢map中找到了，直接返回！
        if (myMap1.find(key) != myMap1.end() && myMap1[key] == (desiredTotal - sum)) {
            return true;
        }

        // 在必输map中找到了，也直接返回！
        if (myMap2.find(key) != myMap2.end() && myMap2[key] == (desiredTotal - sum)) {
            return false;
        }

        // 考察所有可以选的数字
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (sum + nums[i] >= desiredTotal) {
                myMap1[key] = (desiredTotal - sum);
                return true; // 直接就赢了！
            } else {
                mySet.erase(nums[i]);
                bool ret = dfs(mySet, sum + nums[i], desiredTotal, myMap1, myMap2);
                mySet.insert(nums[i]);
                if (ret == false) {
                    myMap1[key] = (desiredTotal - sum);
                    return true;
                }
            }
        }
        
        myMap2[key] = (desiredTotal - sum);

        // 只有当对手在剩余的选择中都必赢的话，就承认自己必输！！
        return false;    
    }    
};

// 作者：hank-36
// 链接：https://leetcode-cn.com/problems/can-i-win/solution/dfsji-yi-hua-sui-ran-hao-shi-bi-jiao-chang-dan-wo-/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


class Solution {
public:
    // 用一个vector记录每次的选择的结果，如果能赢则为1，不能赢则为-1，没有记录则为0，比如：
    // 第一个人选1，第二个人选2或者第一个人选2第二个人选1的前提下，
    // 二进制位为：0000 0110，则v_c[6]的值如果不为零，为1则返回true，为-1则返回false
    vector<char> v_c;
    int M, T;

    bool canIWin(int MM, int TT) {
        // 这里面进行判断，是否可以得到答案，如果整个数组的和小于要求的目标数字，则返回false
        M = MM;
        T = TT;
        if ((1 + M) * M / 2 < T) return false;
        // 这里注意初始化，所有要遍历的数字为2^M个，因此下标要加1
        v_c = vector<char>(1 << (M) + 1, 0);
        return canWin(T, 0);
    }

    bool canWin(int target, int visited) {
        // 如果visited这种模式已经有人选过了，那么返回结果即可
        // 如果没有人选过这种模式，那么在这种模式下把可以选择的数字都选一遍，逐个判断
        if (v_c[visited] != 0) return v_c[visited] == 1;
        for (int i = 1; i <= M; ++i) {
            // 用一个mask记录当前选择了第几个数字
            int mask = (1 << i);
            // 如果mask&visited的结果是0那么第i个数字（也就是i）没有选过
            // 赢的条件：如果选的这个数大于等于目标数字，或者对手在这种情况下是输的，那么，我在这情况下就是赢的
            // 要知道对手在这个情况下是不是输的，就递归canWin(target - i, visited | mask)得到答案即可
            if ((mask & visited) == 0 && (i >= target || !(canWin(target - i, visited | mask)))) {
                v_c[visited] = 1;
                return true;
            }
        }
        // 如果在visited这个模式（前提）下遍历了一圈可以选择的数字都无法赢，那么我就输了
        v_c[visited] = -1;
        return false;
    }

};

2、打表+找规律

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
                //sn为等差数列求和
        int sn = maxChoosableInteger + maxChoosableInteger * (maxChoosableInteger - 1) / 2;
        //如果目标大于sn那不可能赢
        if(desiredTotal > sn) return false;
        //打表数据如下
        if(maxChoosableInteger == 10 && (desiredTotal == 40 || desiredTotal == 54)) return false;
        if(maxChoosableInteger == 20 && (desiredTotal == 210 || desiredTotal == 209)) return false;
        if(maxChoosableInteger == 18 && (desiredTotal == 171 || desiredTotal == 172)) return false;
        if(maxChoosableInteger == 12 && desiredTotal == 49) return true;

        //规律如下：desiredTotal == 1必胜，如果累计值模上最大值余1那必输，否则必胜。（但不一定成立，反例如上打表数据）
        return desiredTotal == 1 || desiredTotal % maxChoosableInteger != 1;
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com