| comments | difficulty | edit_url | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
|
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
示例 1：
输入：maxChoosableInteger = 10, desiredTotal = 11 输出：false 解释： 无论第一个玩家选择哪个整数，他都会失败。 第一个玩家可以选择从 1 到 10 的整数。 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
示例 2:
输入：maxChoosableInteger = 10, desiredTotal = 0 输出：true
示例 3:
输入：maxChoosableInteger = 10, desiredTotal = 1 输出：true
提示:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
我们首先判断可以选择的所有整数的和是否小于目标值，如果是，说明无论如何都无法赢，直接返回 false。
然后，我们设计一个函数 mask 表示当前已选择的整数的状态，s 表示当前的累计和。函数返回值为当前玩家是否能赢。
函数
我们遍历 desiredTotal，或者对手选择 true。
如果没有任何一个选择能让当前玩家赢，那么当前玩家就是输的，返回 false。
为了避免重复计算，我们使用一个哈希表 f 记录已经计算过的状态，键为 mask，值为当前玩家是否能赢。
时间复杂度 maxChoosableInteger。
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
@cache
def dfs(mask: int, s: int) -> bool:
for i in range(1, maxChoosableInteger + 1):
if mask >> i & 1 ^ 1:
if s + i >= desiredTotal or not dfs(mask | 1 << i, s + i):
return True
return False
if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:
return False
return dfs(0, 0)class Solution {
private Map<Integer, Boolean> f = new HashMap<>();
private int maxChoosableInteger;
private int desiredTotal;
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
return false;
}
this.maxChoosableInteger = maxChoosableInteger;
this.desiredTotal = desiredTotal;
return dfs(0, 0);
}
private boolean dfs(int mask, int s) {
if (f.containsKey(mask)) {
return f.get(mask);
}
for (int i = 0; i < maxChoosableInteger; ++i) {
if ((mask >> i & 1) == 0) {
if (s + i + 1 >= desiredTotal || !dfs(mask | 1 << i, s + i + 1)) {
f.put(mask, true);
return true;
}
}
}
f.put(mask, false);
return false;
}
}class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
return false;
}
unordered_map<int, int> f;
function<bool(int, int)> dfs = [&](int mask, int s) {
if (f.contains(mask)) {
return f[mask];
}
for (int i = 0; i < maxChoosableInteger; ++i) {
if (mask >> i & 1 ^ 1) {
if (s + i + 1 >= desiredTotal || !dfs(mask | 1 << i, s + i + 1)) {
return f[mask] = true;
}
}
}
return f[mask] = false;
};
return dfs(0, 0);
}
};func canIWin(maxChoosableInteger int, desiredTotal int) bool {
if (1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal {
return false
}
f := map[int]bool{}
var dfs func(int, int) bool
dfs = func(mask, s int) bool {
if v, ok := f[mask]; ok {
return v
}
for i := 1; i <= maxChoosableInteger; i++ {
if mask>>i&1 == 0 {
if s+i >= desiredTotal || !dfs(mask|1<<i, s+i) {
f[mask] = true
return true
}
}
}
f[mask] = false
return false
}
return dfs(0, 0)
}function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
if (((1 + maxChoosableInteger) * maxChoosableInteger) / 2 < desiredTotal) {
return false;
}
const f: Record<string, boolean> = {};
const dfs = (mask: number, s: number): boolean => {
if (f.hasOwnProperty(mask)) {
return f[mask];
}
for (let i = 1; i <= maxChoosableInteger; ++i) {
if (((mask >> i) & 1) ^ 1) {
if (s + i >= desiredTotal || !dfs(mask ^ (1 << i), s + i)) {
return (f[mask] = true);
}
}
}
return (f[mask] = false);
};
return dfs(0, 0);
}