首页 > 其他分享 >464. 我能赢吗 (Medium)

464. 我能赢吗 (Medium)

时间:2023-03-02 18:57:53浏览次数:49  
标签:10 Medium desiredTotal 464 我能 整数 玩家 int maxChoosableInteger

问题描述

464. 我能赢吗 (Medium)

在 "100 game" 这个游戏中,两名玩家轮流选择从 110 的任意整数,累计整数和,先使得累计整数和
达到或超过 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 <= 20
  • 0 <= desiredTotal <= 300

解题思路

dfs

首先从递归的角度来思考,(事实上这里博弈的角度并没有那么强),第一个玩家选了x,那么对下一个玩家而言,他的desiredTotal就变成了desiredTotal - x,而如果下一个玩家赢了,那么第一个玩家就输了。

状态压缩 + 记忆化搜索

首先注意到,这个题中maxChoosableInteger <= 20,因此我们可以用一个最长不超过20位的二进制数mask来表示数的选择过程,如果mask的第i位为1,说明i还没有被选择过,即还能选;

同时我们可以注意到,desired_total的值直接由mask来决定,因为mask的初始值为2^n - 1,所以写cache数组的时候无需加上desired_total的维度;

注意位运算的优先级是很低的,建议加括号。

代码

class Solution {
  public:
    // 改写成位运算的形式
    bool dfs(int desired_total, int cur_total, int bit20, int max_int, unordered_map<int, int> &ump) {
        if (desired_total <= 0) {
            return false;
        }
        if (bit20 == 0) {
            return true;
        }
        if (ump.find(bit20) != ump.end()) {
            return ump[bit20];
        }
        bool tmp = false;
        int cnt = 1;
        for (int i = max_int - 1; i >= 0; --i) {
            if ((bit20 & (1 << i)) != 0) { // 说明数i + 1还没有被选
                int mask = (bit20 ^ (1 << i));
                tmp = tmp || (!dfs(desired_total - i - 1, cur_total + i + 1, mask, max_int, ump));
            }
            if (tmp) {
                ump[bit20] = true;
                return ump[bit20];
            }
        }
        ump[bit20] = false;
        return ump[bit20];
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= maxChoosableInteger) {
            return true;
        }
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal)
            return false;
        unordered_map<int, int> ump;
        int bit20 = (1 << maxChoosableInteger) - 1;
        return dfs(desiredTotal, 0, bit20, maxChoosableInteger, ump);
    }
};

标签:10,Medium,desiredTotal,464,我能,整数,玩家,int,maxChoosableInteger
From: https://www.cnblogs.com/zwyyy456/p/17172994.html

相关文章

  • 1405. 最长快乐字符串 (Medium)
    问题描述1405.最长快乐字符串(Medium)如果字符串中不含有任何'aaa','bbb'或'ccc'这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。给你三个整数a,b,c......
  • 1140. 石子游戏 II (Medium)
    问题描述1140.石子游戏II(Medium)爱丽丝和鲍勃继续他们的石子游戏。许多堆石子排成一行,每堆都有正整数颗石子piles[i]。游戏以谁手中的石子最多来决出胜负。爱丽丝......
  • 179. 最大数 (Medium)
    问题描述179.最大数(Medium)给定一组非负整数nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个字符串而......
  • 524. 通过删除字母匹配到字典里最长单词 (Medium)
    问题描述524.通过删除字母匹配到字典里最长单词(Medium)给你一个字符串s和一个字符串数组dictionary,找出并返回dictionary中最长的字符串,该字符串可以通过删除s......
  • 89. 格雷编码 (Medium)
    问题描述89.格雷编码(Medium)n位格雷码序列是一个由2ⁿ个整数组成的序列,其中:每个整数都在范围[0,2ⁿ-1]内(含0和2ⁿ-1)第一个整数是0一个整数在序列......
  • 397. 整数替换 (Medium
    问题描述397.整数替换(Medium)给定一个正整数n,你可以做如下操作:如果n是偶数,则用n/2替换n。如果n是奇数,则可以用n+1或n-1替换n。返回n变为......
  • 1238. 循环码排列 (Medium)
    问题描述1238.循环码排列(Medium)给你两个整数n和start。你的任务是返回任意(0,1,2,,...,2^n-1)的排列p,并且满足:p[0]=startp[i]和p[i+1]的二进制表示形......
  • 1792. 最大平均通过率 (Medium)
    问题描述1792.最大平均通过率(Medium)一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组classes,其中classes[i]=[pass......
  • 132 模式 (Medium)
    问题描述456.132模式(Medium)给你一个整数数组nums,数组中共有n个整数。132模式的子序列由三个整数nums[i]、nums[j]和nums[k]组成,并同时满足:i<j<k......
  • 1139. 最大的以 1 为边界的正方形 (Medium)
    问题描述1139.最大的以1为边界的正方形(Medium)给你一个由若干0和1组成的二维网格grid,请你找出边界全部由1组成的最大正方形子网格,并返回该子网格中的元素......