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

[freesan44]

class Solution {
    func canIWin(_ maxChoosableInteger: Int, _ desiredTotal: Int) -> Bool {
        if desiredTotal <= maxChoosableInteger {
            return true
        }
        if (1...maxChoosableInteger).reduce(0, +) < desiredTotal {
            return false
        }

        var memo: [Int: Bool] = [:]

        func dp(_ picked: Int, _ acc: Int) -> Bool {
            if acc >= desiredTotal {
                return false
            }
            if picked == (1 << (maxChoosableInteger + 1)) - 1 {
                return false
            }
            if let result = memo[picked] {
                return result
            }

            for n in 1...maxChoosableInteger {
                if picked & (1 << n) == 0 {
                    if !dp(picked | (1 << n), acc + n) {
                        memo[picked] = true
                        return true
                    }
                }
            }
            memo[picked] = false
            return false
        }

        return dp(0, 0)
    }
}

[Diana21170648]

思路

动态规划

代码

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

        @lru_cache(None)
        def dp(picked, acc):
            if acc >= desiredTotal:
                return False
            if picked == (1 << (maxChoosableInteger + 1)) - 1:
                return False
            for n in range(1, maxChoosableInteger + 1):
                if picked & 1 << n == 0:
                    if not dp(picked | 1 << n, acc + n):
                        return True
            return False

        return dp(0, 0)

复杂度分析

• 时间复杂度：O(2^m)
• 空间复杂度：O(2^m)

[GuitarYs]

class Solution:
    def canWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= 0:
            return True
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal:
            return False
        self.memo = {}
        def canWinHelper(used: int, total: int) -> bool:
            if total <= 0:
                return False
            if used in self.memo:
                return self.memo[used]

            for i in range(1, maxChoosableInteger + 1):
                if not used & (1 << (i - 1)):
                    if not canWinHelper(used | (1 << (i - 1)), total - i):
                        self.memo[used] = True
                        return True
            self.memo[used] = False
            return False
        return canWinHelper(0, desiredTotal)

[snmyj]

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;
        }
    }
}

[Fuku-L]

代码

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

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

    private boolean dfs(int state, int desiredTotal, Boolean[] dp, int maxChoosableInteger){
        if(dp[state] != null){
            return dp[state];
        }

        for(int i = 1; i <= maxChoosableInteger; i++){
            int cur = 1 << (i - 1);
            if((cur & state) != 0){
                continue;
            }

            if(i >= desiredTotal || !dfs(cur|state, desiredTotal - i, dp, maxChoosableInteger)){
                return dp[state] = true;
            }
        }
        return dp[state] = false;
    }
}

[Momogir]

使用dfs方法

记录当前已经使用的数字集合usedNumbers(使用0,1的数字序列表示.0表示未使用,1表示使用)

记录当前的所有数字的和desiredTotal

时间复杂度O(2^n x n)

空间复杂度O(2^n)

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

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

[Beanza]

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

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

[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，所有数字都没有被使用