leetcode 464 Can I Win

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

---

• 假设有一个函数dfs，它返回当前的剩余数字集合下，我能否一定能赢。
• 那么他的处理过程是，他在剩余数字集合抽取一个数字，并将desireTotal减掉这个数字，表示我当前选择这个数字，然后对手调用这个函数，判断他能否一定能赢。
  • 如果对手调用这个函数后，返回false，则说明我在选择这个数字后，对手肯定输了，那么我肯定赢了。
  • 如果对手调用这个函数后，返回true，则说明，我这么选对手能赢，那么我需要换一个数字选。
  • 当所有的可选则的数字我都选了一遍后，我都赢不了，那么我就肯定赢不了了。
• 那么对于剩下的数字集合，我们需要用一个变量每个数字的状态，判断它是否可以选择。由于题目中限定了最多不超过20，这样一来，我们可以用一个整数key来存每个数字的状态，这个key中，第i位是否为1来判断数字i是否可选。
• 那么对于一个给定的desireTotal，我们如何判断当前我的输赢状态呢？
  • 首先，如果在dfs中，假设经过若干轮迭代，当前轮到我选择数组，此时，我发现desireTotal小于等于0，这就说明，在上一轮对手已经让场面上的数字之和大于desireTotal了，那么对手已经赢了，我输了，此时，dfs应该返回false
  • 如果desireTotal大于0，此时，我需要从剩余数字集合中依次抽取数字，进行判断。

---

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        // desiredTotal < 2 肯定我能赢
        if (desiredTotal <2 )
            return true;
        // 总共的可选数字加起来都小于desiredTotal，两个人都不能赢
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal)
            return false;
        HashMap<Integer, Boolean> map = new HashMap<>();
        int key = 0;
        // key中的第位为1，表明i可以选择。
        for (int i=1; i<= maxChoosableInteger; i++) {
            key |= (1 << i);
        }
        return dfs(map, key, maxChoosableInteger, desiredTotal);
    }
    
    boolean dfs(HashMap<Integer, Boolean> map, int key, int maxChoosableInteger, int desiredTotal) {
        if (map.containsKey(key))
            return map.get(key);
      	// 当desiredTotal小于等于0时，说明对方在上一把已经赢了
        if (desiredTotal <= 0)
            return false;
      	// 遍历取走一个，判断能否赢
        for (int i=1; i<=maxChoosableInteger; i++) {
            if ( (key & (1<<i)) != 0) {
                key = key - (1<<i);
                if (!dfs(map, key, maxChoosableInteger, desiredTotal-i)) {
                    // 这里注意将key放入map，注意key要还原成输入的样子
                    key = key + (1<<i);
                    map.put(key, true);
                    return true;
                }
                // 这里也需要注意
                key = key + (1<<i);
            }
        }
        map.put(key, false);
        return false;
    }
}

---

Python Version:

• 注意这里是无放回的要求，所以需要记录下每一个数的状态。

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if desiredTotal > maxChoosableInteger * (maxChoosableInteger + 1) / 2:
            return False
        if desiredTotal <= maxChoosableInteger:
            return True
        memo = {}
        key = range(1, maxChoosableInteger+1, 1)
        return self.helper(maxChoosableInteger, desiredTotal, memo, key)

    def helper(self, maxChoosableInteger, desiredTotal, memo, key):
        idx = str(key)
        if idx in memo:
            return memo[idx]
        if desiredTotal <=0:
            return False
        if key[-1] > desiredTotal:
            return True
        for i in range(len(key)):
            t = key[:i] + key[i+1:]
            if not self.helper(maxChoosableInteger, desiredTotal-key[i], memo, t):
                memo[idx] = True
                return True
        memo[idx] = False
        return False

• bit manipulation

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if desiredTotal > maxChoosableInteger * (maxChoosableInteger + 1) / 2:
            return False
        if desiredTotal <= maxChoosableInteger:
            return True
        memo = {}
        key = 0 # 每一位上如果是0，表示没有被用过
        return self.helper(maxChoosableInteger, desiredTotal, memo, key)

    def helper(self, maxChoosableInteger, desiredTotal, memo, key):
        if key in memo:
            return memo[key]
        if desiredTotal <=0:
            return False
        for i in range(maxChoosableInteger):
            if not (key & (1<<i)):
                # 注意这里是desiredTotal-(i+1)
                if not self.helper(maxChoosableInteger, desiredTotal-(i+1), memo, key ^ (1 << i)):
                    memo[key] = True
                    return True
        memo[key] = False
        return False