力扣:464. 我能赢吗
前言
昨天在力扣刷了下这题,发现这题比想象的要绕一些,而看了官方题解后,发现自己还有很多知识待学习了解,比如位运算的运用等,特此在此做个记录,并分析下这题的解法思路。
题目
在 "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
分析
这题的话其实就是两个玩家从一个数字池中轮流取数字,取到的数字不能放回,并将取到的数字累加起来,而如果谁先让累加的和达到目标值,则获胜,题目要求先手的玩家无论怎样选数字都获胜,才胜利,故只需要对手获胜的话,就算失败。
而这里的话每个数字就只有两种状态,已使用或者未使用,可以用一维数组标记每个数字是否使用过,但题意规定的数字范围只有 1~20,故我们可以将一维数字改为用二进制数表示,而int类型有32个bit位,故我们可以将已使用的数字在对应的位置标记为1,未使用则为0即可。
这里举个例子,假设有10位标志位
sh
# 初始标志位
0 0 0 0 0 0 0 0 0 0 ->int 0
# 此时,A玩家从数字池中取走了 数字9,则
0 1 0 0 0 0 0 0 0 0 ->int 512 0|1<<9
# 这里解释下:
1<<9 相当于 1 * 2^9 = 512,也就是 0100000000
而与 0进行或运算,则:
0000000000
0100000000
----------
0100000000
故可以标记当前 数字9 已被取走。
# 假如接下来B玩家取走了 数字7,则
0 1 0 1 0 0 0 0 0 0 ->int 640 512|(1<<7)
0100000000
0001000000
----------
0101000000
# 那接下来又轮到A玩家取数字,此时他需判断数字7是否被取走了,则需右移7位数字,判断第7个数字的标志位是否为1
(640>>7) & 1
0101000000
右移后:
0000000101
与1与运算
0000000001
----------
0000000001
故数字7已被使用
通过上述例子,我们很好理解了利用二进制数字来标记一定范围内的数字,大大减少空间和提升效率。
当然,我们判断也可以改为使用
sh
usedNumbers & (1<<i) # 来判断数字i是否被使用
usedNumbers | (1>>i) # 来标记数字i已经被使用
知道如何判断数字是否被使用过后,那我们还可以进行优化判断,选择了某一些数字时的结果已经知道是否能赢后,我们就进行记录,减少重复计算。
故该题我们用记忆化搜索 + 状态压缩的方法进行解题,是一种动态规划算法。
答案
这里我就已官方的题解稍微修改,并添加注释,更好的理解这块程序的运行。
java
import java.util.*;
public class M_464 {
public static void main(String[] args) {
System.out.println(canIWin(10, 11));
// System.out.println(canIWin(10, 0));
// System.out.println(canIWin(10, 1));
// System.out.println(canIWin(3, 5));
}
// 记忆化的hashMap,用来记录选择了哪些树的情况,当前玩家的胜负;用以减少时间复杂度
static Map<Integer, Boolean> memo = new HashMap<>();
/**
* 在 "100 game" 这个游戏中,两名玩家轮流选择从 1 到 10 的任意整数,累计整数和,先使得累计整数和 达到或超过 100 的玩家,即为胜者。
*/
public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// 如果所有数字之和都小于目标值,那么肯定谁都无法赢
if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
return false;
}
// 否则的话递归判断,判断先手能不能赢,需要注意的是,先手从0开始
return dfs(maxChoosableInteger, 0, desiredTotal, 0);
}
/**
* 深度搜索
*
* @param maxChoosableInteger 供选择的数最大范围
* @param usedNumbers 被选择的数,注意用二进制表示。如0010则表示2已经被选择,0001则表示1已被选择
* @param desiredTotal 累计整数和需要超过的目标值
* @param currentTotal 当前累计整数和
*/
public static boolean dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
// 如果选择这个数字时的结果未计算过,则对其进行处理并存储起来
if (!memo.containsKey(usedNumbers)) {
boolean res = false; // 当前这种情况的输赢情况
// 循环遍历整数池中的数字
for (int i = 1; i <= maxChoosableInteger; i++) {
// 若这个数还没被选择,才往下做逻辑,否则进入下一轮循环
// 这里判断以二进制位 比如取走数字2,一开始的usedNumbers为0,取走后为 0010,
// 而这时 i 是 1,则判断第i位的数字二进制,与当前已选择的数进行与运算,如果对应位置的数字为1,则与运算的结果不为0
if ((usedNumbers & (1 << i)) == 0) {
// 当前数字可以使累加和达到或超过目标值
if (i + currentTotal >= desiredTotal) {
res = true; // 则标记当前这种情况可以赢
break;
}
// 否则的话,递归判断,我选完后,对方选完是不是就输了;对方输了,我自然就赢了
// usedNumbers | (1 << i) usedNumbers为已经取走的数字的二进制数标志
// 然后 1<<i,得到的是数字i的二进制标志数,在二进制数中的第i位标记为1,之后进行或运算,则在usedNumbers中标记第i位的数字已被取走,
if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i)) {
res = true;
break;
}
}
}
// 将当前状态及对应的结果存入记忆化搜索中,避免重复计算
memo.put(usedNumbers, res);
}
return memo.get(usedNumbers);
}
}
