【Day 60 】2022-12-30 - 464. 我能赢么

[azl397985856]

464. 我能赢么

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

在 "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），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

[snmyj]

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        import functools
        if  desiredTotal <= maxChoosableInteger: return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal: return False

        @functools.lru_cache(None)
        def dfs(used, desiredTotal):
            for i in range(maxChoosableInteger):
                cur = 1 << i
                if cur & used == 0:
                    if desiredTotal <= i + 1 or not dfs(cur | used, desiredTotal - i - 1):
                        return True
            return False

        return dfs(0, desiredTotal)

[whoam-challenge]

class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: if maxChoosableInteger >= desiredTotal: return True if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: return False

    def dfs(state, desiredTotal, dp):
        if dp[state] != None:
            return dp[state]
        for i in range(1, maxChoosableInteger + 1):
            cur = 1 << (i - 1)
            if cur & state != 0:
                continue

            if i >= desiredTotal or not dfs(cur | state, desiredTotal - i, dp):
                dp[state] = True
                return True
        dp[state] = False
        return False

    return dfs(0, desiredTotal, [None] * (1 << maxChoosableInteger))

[Alexno1no2]

抄袭大法好

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        # 剪枝1：如果 所有数加起来 不足，那么谁都不可能赢
        if (maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal:
            return False
        # 剪枝2：先手直接选 maxChoosableInteger稳赢
        if maxChoosableInteger >= desiredTotal:
            return True

        @cache # 记忆搜索，算过的状态直接用结果，不用再重复算
        def dfs(cur, state): # cur：当前和，state位运算用来表示 数字们的使用状态
            for i in range(1, maxChoosableInteger + 1): # 遍历 1 到 maxChoosableInteger 位置，找能让我赢的 数字 i
                if not (1 << i) & state: # 如果 state中 i 位置是0，数字 i 没有被使用，那么接下来就用数字 i
                    if cur + i >= desiredTotal or not dfs(cur + i, state | (1 << i)): # 两种赢，要么我到目的了，要么你在后面的回合不可能赢，注意 当前和 + i，以及 数字i 被使用了
                        return True
            return False
        return dfs(0,0) # 初始状态，当前和为0，所有数字都没有被使用```

[testplm]

class Solution:
    def canIWin(self, maxChoosableInteger, desiredTotal):
        def dfs_rec_memo(total,num_used):
            if(tuple(num_used) in cache):
                return cache[tuple(num_used)]
            for num in range(1,maxChoosableInteger + 1):
                if(not num_used[num]):
                    if(total +num>=desiredTotal):
                        cache[tuple(num_used)] = True
                        return True
                    num_used[num] = True
                    if(not dfs_rec_memo(total+num,num_used)):
                        num_used[num] = False
                        cache[tuple(num_used)] = True
                        return True
                    num_used[num] = False
            cache[tuple(num_used)] = False
            return False
        if(1+maxChoosableInteger)*maxChoosableInteger//2 < desiredTotal:
            return False

        cache = {}
        num_used = [False]*(maxChoosableInteger+1)
        return dfs_rec_memo(0,num_used)

[bookyue]

code

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal)
            return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal)
            return false;

        return dfs(0, 0, maxChoosableInteger, desiredTotal, new int[1 << 21]);
    }

    private boolean dfs(int state, int sum, int maxChoosableInteger, int desiredTotal, int[] visited) {
        if (visited[state] == 1) return true;
        if (visited[state] == 2) return false;

        for (int num = 1; num <= maxChoosableInteger; num++) {
            if (((state >> num) & 1) == 1) continue;

            if (sum + num >= desiredTotal) {
                visited[state] = 1;
                return true;
            }

            if (!dfs(state | (1 << num), sum + num, maxChoosableInteger, desiredTotal, visited)) {
                visited[state] = 1;
                return true;
            }
        }

        visited[state] = 2;
        return false;
    }

[Abby-xu]

思路

抄答案DFS+bitmask

代码

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        @cache
        def dfs(usedNumbers, currentTotal):
            for i in range(1, maxChoosableInteger + 1):
                if (usedNumbers >> i) & 1 == 0:
                    if currentTotal + i >= desiredTotal or not dfs(usedNumbers | (1 << i), currentTotal + i):
                        return True
            return False

        return ((1 + maxChoosableInteger) * maxChoosableInteger) >> 1 >= desiredTotal and dfs(0, 0)

复杂度

...

[Elsa-zhang]

''' 464. 我能赢么
    判断先出手的玩家是否能稳赢
'''

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int):
        # def dfs(totol):
        #     if totol>=desiredTotal: return False

        #     for i in range(1, maxChoosableInteger+1):
        #         if not dfs(totol+i):
        #             return True

        #     return False

        # return dfs(0)

        if desiredTotal <= maxChoosableInteger: return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal: return False

        def dfs(picked, acc):
            if acc >= desiredTotal: return False
            if len(picked) == maxChoosableInteger: return False

            for n in range(1, maxChoosableInteger + 1):
                if n not in picked:
                    picked.add(n)
                    if not dfs(picked, acc + n):
                        picked.remove(n)
                        return True
                    picked.remove(n)
            return False

        return dfs(set(), 0)

[zywang0]

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        import functools
        if  desiredTotal <= maxChoosableInteger: return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal: return False

        @functools.lru_cache(None)
        def dfs(used, desiredTotal):
            for i in range(maxChoosableInteger):
                cur = 1 << i
                if cur & used == 0:
                    if desiredTotal <= i + 1 or not dfs(cur | used, desiredTotal - i - 1):
                        return True
            return False

        return dfs(0, desiredTotal)

[tiandao043]

思路

状态压缩dp每一位表示第i个位置是否被选

代码

class Solution {
public:
    int maxChoosableInt; 
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        maxChoosableInt=maxChoosableInteger;
        int sum=(1+maxChoosableInteger)*maxChoosableInteger/2;
        // cout<<sum<<endl;
        if(sum<desiredTotal)return false;
        if(maxChoosableInteger>=desiredTotal)return true;
        unordered_map<int,int> d;
        return dfs(0,desiredTotal,0,d);
    }
    bool dfs(int s,int t,int S,unordered_map<int,int>& d){
        if(d[S])return d[S];
        int& ans=d[S];
        if(s>=t)return ans=true;
        // if(S==(((1<<maxChoosableInt)-1)<<1))return ans=false;//11111110
        if(S == (1 << (maxChoosableInt + 1)) - 1)return false;

        for(int m=1;m<=maxChoosableInt;++m){
            if(S&(1<<m))continue;//第m位是否为1，in 操作符
            int nextS=S|(1<<m);//add 操作
            if(s+m>=t)return ans=true;
            bool r1=dfs(s+m,t,nextS,d);
            if(!r1)return ans=true;
        }
        return ans=false;
    }
};

O(2^n×n) O(2^n)

[A-pricity]

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function(maxChoosableInteger, desiredTotal) {

    // 先处理边界情况
    if (maxChoosableInteger >= desiredTotal) {
        return true
    } else if ((1+maxChoosableInteger)*maxChoosableInteger < 2*desiredTotal) {
        return false
    }
    // } else if (maxChoosableInteger % 2 === 1) {
    //     return false
    // } else if (((desiredTotal-1) % (maxChoosableInteger+2) === 0 
    // || desiredTotal % max === 0 ) 
    // && maxChoosableInteger % 2 === 0) {
    //     return true
    // } else {
    //     return false
    // }

    // 还是得用dfs，深度优先搜索+记忆化存储
    // state上用二进制的每一位表示这个数是否被使用过，1表示使用过，0表示没有使用过
    // state = 9 (001001) 表示1、4使用过
    // 判断当前数i+1是否已经使用过的方法:
    // 右移位运算a >> i 相当于把a的二进制数往右移动i位，也就是a / (2^i) 取整
    // 9 >> 3 = 1，再和1按位与（1的前面所有都是0），判断最后一位是不是1。 1 & 1 = 1， 1&2 = 0
    // state >> i & 1 === 1， 则i+1在state中使用过，也就是state右边数第i+1位是1。
    // 往state中更新某一个数被新使用,按位或或者相加：state & (1<<i) 比如 9 | (1<<5) = 9 & 32 = 41
    // state和currentTotal有关联关系。对特定题目的desiredTotal 和 maxChoosableInteger, dfs(state) 的结果唯一
    // 记忆化体现在对于计算过的特定的state的dfs结果是true还是false，要缓存起来
    let dfsRes = new Map()
    // 初始的state=0， currentTotal也是0
    const dfs=(state, maxChoosableInteger, currentTotal, desiredTotal) => {
        // console.log(`${state.toString(2)}`,{currentTotal},' 49 line')
        if (dfsRes.has(state)) {
            return dfsRes.get(state)
        } else {
            for (let i=0; i<maxChoosableInteger; i++) {
                // 如果第i + 1个数用过了，跳过
                if ((state >> i) & 1 === 1) {
                    continue
                }
                // state = state + (1 << i) // 错了，state和currentTotal不能每次都累加
                // currentTotal += i + 1
                // console.log(`${state.toString(2)}`,{currentTotal})
                if (currentTotal + i + 1 >= desiredTotal) {
                    dfsRes.set(state, true) // 不是 state + (1 << i)
                    // console.log('here 62')
                    return true
                } else if (!dfs(state + (1 << i), maxChoosableInteger, currentTotal + i + 1, desiredTotal)) { // 如果下个递归调用者最终返回是false，表示我还是能赢
                    dfsRes.set(state, true) // 只是表示当前state当前玩家可以必胜
                    console.log('here 66')
                    return true
                }
            }
            dfsRes.set(state, false)
            return false
        } 
    }
    return dfs(0, maxChoosableInteger, 0, desiredTotal)
}

[buer1121]

class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

暴力法

    if desiredTotal <= maxChoosableInteger:
        return True
    if sum(range(maxChoosableInteger + 1)) < desiredTotal:
        return False
    # picked 用于保存当前已经选择过的数。
    # acc 表示当前累计的数字和
    def backtrack(picked, acc):
        if acc >= desiredTotal:
            return False
        if len(picked) == maxChoosableInteger:
            # 说明全部都被选了，没得选了，返回 False， 代表输了。
            return False
        for n in range(1, maxChoosableInteger + 1):
            if n not in picked:
                picked.add(n)
                # 对方有一种情况赢不了，我就选这个数字就能赢了，返回 true，代表可以赢。
                if not backtrack(picked, acc + n):
                    picked.remove(n)
                    return True
                picked.remove(n)
        return False

    # 初始化集合，用于保存当前已经选择过的数。
    return backtrack(set(), 0)

    ###dfs法
    #特殊情况判定，如果maxChoosableInteger对应的所有数之和小于desiredTotal则永远无法赢
    if (1+maxChoosableInteger)*maxChoosableInteger//2<desiredTotal:
        return False
    @cache
    #dfs函数是当前可选择的数字，已选择的数字之和
    def dfs(state,choosed_sum):
        #遍历当前可选数字
        for x in range(maxChoosableInteger):
            #需要根据state确定x是否已使用
            if (1<<x)&state:
                continue
            #如果选择X后sum大于desiredTotal
            if choosed_sum+x+1>=desiredTotal or not dfs((1<<x)|state,choosed_sum+x+1):
                return True
        return False
    return dfs(0,0)

[JancerWu]

class Solution {
    Map<Integer, Boolean> memory = new HashMap<>();
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        return dfs(maxChoosableInteger, desiredTotal, 0, 0);
    }
    public boolean dfs(int maxChoosableInteger, int desiredTotal, int select, int sum) {
        if (!memory.containsKey(select)) {
            boolean status = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((select >> i) & 1) == 0) {
                    if (sum + i + 1 >= desiredTotal) {
                        status = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, desiredTotal, select | (1 << i), sum + i + 1)) {
                        status = true;
                        break;
                    }
                }
            }
            memory.put(select, status);
        }
        return memory.get(select);
    }
}

[RestlessBreeze]

code

class Solution {
public:
    unordered_map<int, bool> memo;

    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        return dfs(maxChoosableInteger, 0, desiredTotal, 0);
    }

    bool dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
        if (!memo.count(usedNumbers)) {
            bool res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((usedNumbers >> i) & 1) == 0) {
                    if (i + 1 + currentTotal >= desiredTotal) {
                        res = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
                        res = true;
                        break;
                    }
                }
            }
            memo[usedNumbers] = res;
        }
        return memo[usedNumbers];
    }
};

[klspta]

class Solution {

    private int[] dp;
    private int n;
    private int m;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        n = maxChoosableInteger;
        m = desiredTotal;
        if(n * (n + 1) / 2 < m){
            return false;
        }
        dp = new int[1 << n + 1];
        Arrays.fill(dp, -1);
        return process(0) == 1;
    }

    private int process(int x){
        if(dp[x] != -1){
            return dp[x];
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            if((x >> i & 1) == 1){
                sum += i + 1;
            }
        }
        for(int i = 0; i < n; i++){
            if((x >> i & 1) == 1){
                continue;
            }
            if(sum + i + 1 >= m){
                dp[x] = 1;
                return 1;
            }
            if(process(x + (1 << i)) == 0){
                dp[x] = 1;
                return 1;
            }
        }
        dp[x] = 0;
        return 0;
    }
}

[GG925407590]

class Solution {
public:
    unordered_map<int, bool> memo;

    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        return dfs(maxChoosableInteger, 0, desiredTotal, 0);
    }

    bool dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
        if (!memo.count(usedNumbers)) {
            bool res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((usedNumbers >> i) & 1) == 0) {
                    if (i + 1 + currentTotal >= desiredTotal) {
                        res = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
                        res = true;
                        break;
                    }
                }
            }
            memo[usedNumbers] = res;
        }
        return memo[usedNumbers];
    }
};

[mayloveless]

思路

复制官方题解..

代码

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
  // 如果可选值大于目标值，说明可以选一个大于的数字，直接获胜
  if (maxChoosableInteger >= desiredTotal) return true;

  // 全部拿完也无法到达
  var sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2;
  if (desiredTotal > sum) return false;

  // 记忆化
  var dp = {};

  /**
   * @param {number} total 剩余的目标值
   * @param {number} state 使用二进制位表示抽过的状态
   */
  function f(total, state) {
    // 有缓存
    if (dp[state] !== undefined) return dp[state];

    for (var i = 1; i <= maxChoosableInteger; i++) {
      var curr = 1 << i;
      // 已经抽过这个数
      if (curr & state) continue;
      // 直接获胜
      if (i >= total) return (dp[state] = true);
      // 如果对方输，则自己赢
      if (!f(total - i, state | curr)) return (dp[state] = true);
    }

    // 没有任何让对方输的方法
    return (dp[state] = false);
  }

  return f(desiredTotal, 0);
};

复杂度

时间：O(2^n *n) 空间：O(2^n )

[Jetery]

code(java)

class Solution {
    public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        int[] dp = new int[1 << maxChoosableInteger];
        Arrays.fill(dp, -1);
        return dfs(desiredTotal, 0, maxChoosableInteger, dp) == 1;
    }

    public static int dfs(int total, int state, int max, int[] dp) {
        if (dp[state] != -1) return dp[state];
        for (int i = 0; i < max; i++) {
            if (((state >> i) & 1) == 1) continue;
            if (total <= i + 1) return dp[state] = 1; 
            if (dfs(total - i - 1, state | (1 << i), max, dp) == 0) return dp[state] = 1; 
        }
        return dp[state] = 0;
    }
}

[paopaohua]

class Solution {
    public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        int[] dp = new int[1 << maxChoosableInteger];
        Arrays.fill(dp, -1);
        return dfs(desiredTotal, 0, maxChoosableInteger, dp) == 1;
    }

    public static int dfs(int total, int state, int max, int[] dp) {
        if (dp[state] != -1) return dp[state];
        for (int i = 0; i < max; i++) {
            if (((state >> i) & 1) == 1) continue;
            if (total <= i + 1) return dp[state] = 1; 
            if (dfs(total - i - 1, state | (1 << i), max, dp) == 0) return dp[state] = 1; 
        }
        return dp[state] = 0;
    }
}

[chenming-cao]

解题思路

参考官方题解和yanglr的题解。状压动态规划 + 回溯 + 位运算。用二进制数表示状态。用Boolean数组储存不同状态的结果，使用记忆化搜索。

边界情况：最大可选数字大于等于累计和，必胜；所有可选数字和小于累计和，必败。 一般情况：第一位玩家先手。第一位玩家选完之后，第二位玩家变成先手情况（状态转移）。如果第一位玩家在当前状态下可以获胜，或者可以让下一轮第二位玩家必败，则第一位玩家必胜。如果遍历各种情况第一位玩家都无法胜利，则必败。

代码

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        // two special cases
        // 1. if maxChoosableInteger >= desiredTotal, play1 can win with only one move
        if (maxChoosableInteger >= desiredTotal) return true;
        // 2. if sum of all available integers at the beginning of the game is less than desiredTotal,
        // play1 cannot win
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        // use a memo array to store the results of possible states (number represented by 20 bits)
        // use Boolean here as the default value is null, cannot use boolean because its default value is false
        // and we cannot know whether it is filled
        Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1]; // length = 2^maxChoosableInteger - 1
        return dfs(maxChoosableInteger, desiredTotal, 0, dp);
    }

    private boolean dfs(int maxChoosableInteger, int total, int state, Boolean[] dp) {
        // if the result of the state is in the array, directly return the result
        if (dp[state] != null) return dp[state];
        // check each available integer and fill the array
        for (int i = 1; i <= maxChoosableInteger; i++) {
            int temp = 1 << (i - 1); // record the integer to be added to the state
            // if current integer is not added in the state
            if ((temp & state) == 0) { // the corresponding bit in the state is 0
                // if adding i will reach or exceed the total 
                // or we can make sure the player2 cannot win after this move, then player1 can win 
                if (total - i <= 0 || !dfs(maxChoosableInteger, total - i, state | temp, dp)) { 
                    dp[state] = true;
                    return true;
                }
            }
        }
        // otherwise, player1 will not win
        dp[state] = false;
        return false;
    }
}

复杂度分析

• 时间复杂度：O(2^N)，N为maxChoosableInteger
• 空间复杂度：O(2^N)

[FlipN9]

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= maxChoosableInteger || desiredTotal == 0)
            return true;
        if (desiredTotal > ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2))
            return false;

        if (1 + maxChoosableInteger < desiredTotal && desiredTotal < 2 * maxChoosableInteger)
            return true;
        if (1 + maxChoosableInteger == desiredTotal && desiredTotal < 2 * maxChoosableInteger)
            return false; 

        if (desiredTotal % 2 == 0 && maxChoosableInteger % 2 == 0) {
            return desiredTotal / maxChoosableInteger < 4 || desiredTotal == 100 && maxChoosableInteger == 16;
        } else {
            return desiredTotal % 2 == 0 || maxChoosableInteger % 2 != 0 || desiredTotal / maxChoosableInteger < 5;
        }
    }
}