LeetCode 464. Can I Win 2019-06-21

题目描述

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

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

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

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

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

tag

博弈题 博弈 DFS 记忆化

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
maxChoosableInteger = 10
desiredTotal = 11

输出:
false

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

算法1

(暴力枚举) O()
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

def can_win(choices, remainder):
# 直接选最大那个就能赢
if choices[-1] >= remainder:
return True

# 元组才可哈希
seen_key = tuple(choices)
if seen_key in seen:
return seen[seen_key]

for index in range(len(choices)):
# 第二个玩家不能赢,意味着第一个玩家能赢
if not can_win(choices[:index] + choices[index + 1:], remainder - choices[index]):
seen[seen_key] = True
return True

seen[seen_key] = False
return False


choices = [i for i in range(1, maxChoosableInteger + 1)]
sum_choices = (1 + maxChoosableInteger) * maxChoosableInteger // 2

if sum_choices < desiredTotal:
return False

# 奇数个选择时能确保赢
if sum_choices == desiredTotal and len(choices) % 2 == 1:
return True

seen = {}

return can_win(choices, desiredTotal)

位运算加速

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

def can_win(maxChoosableInteger, desiredTotal, bit_mask):
if bit_mask in seen:
return seen[bit_mask]

for i in range(maxChoosableInteger):
# 枚举每种情况,只能是0变成1,1不能变成0
if (bit_mask >> i) & 1:
continue
if i + 1 >= desiredTotal or not can_win(maxChoosableInteger, desiredTotal - (i + 1), bit_mask | (1 << i)):
seen[bit_mask] = True
return True

seen[bit_mask] = False
return False


choices = [i for i in range(1, maxChoosableInteger + 1)]
sum_choices = (1 + maxChoosableInteger) * maxChoosableInteger // 2

if sum_choices < desiredTotal:
return False

# 奇数个选择时能确保赢
if sum_choices == desiredTotal and len(choices) % 2 == 1:
return True

if maxChoosableInteger >= desiredTotal:
return True

seen = {}
bit_mask = 1 << maxChoosableInteger
return can_win(maxChoosableInteger, desiredTotal, bit_mask)