leetcode464. Can I Win

题目要求

In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input: maxChoosableInteger = 10 desiredTotal = 11

Output: false

Explanation: No matter which integer the first player choose, the first player will lose. The first player can choose an integer from 1 up to 10. If the first player choose 1, the second player can only choose integers from 2 up to 10. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal. Same with other integers chosen by the first player, the second player will always win.

现在有1~n这n个整数,两个人轮流从这n个数中任意选1个数(数字不能重复选择),假如两个人都用最优方法来选取数字,问玩家一是否一定能够获胜。

思路和代码

像这种轮流选择的题目,其实通过深度优先遍历的方式来穷尽所有的结果,就一定可以的得出结论。但是穷尽可能会出现O(n!)的时间复杂度并导致超市,因此尽可能的记录过程中得出的结论就可以提高时间复杂度。

这题的中间过程有哪些呢:

  1. 剩余还没有选择的数字
  2. 想要得到的目标数字

但是其实我们可以知道,2可以通过(1~n)的数字和减去所有已经选择的数字得出,因此我们只要记录中间结果1即可。而中间结果如何记录呢?可以通过位式图来记录每一位被选择的情况,以及这种选择情况是否一定能够让第一个选择的玩家获胜。举个例子,如1~5,其中选中了(1,3),则位式图为00101.

代码如下:

    Map<Integer, Boolean> map = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        int sum = (maxChoosableInteger + 1) * maxChoosableInteger / 2;
        if (sum < desiredTotal) return false;
        boolean[] selected = new boolean[maxChoosableInteger+1];
        return helper(desiredTotal, selected);
    }

    public boolean helper(int desiredTotal, boolean[] selected) {
        if (desiredTotal <= 0) return false;
        int symbol = format(selected);
        if (map.containsKey(symbol)) {
            return map.get(symbol);
        }
        int size = selected.length;
        for (int i = 1 ; i< size ; i++) {
            if (!selected[i]) {
                selected[i] = true;
                if (!helper(desiredTotal-i, selected)) {
                    selected[i] = false;
                    map.put(symbol, true);
                    return true;
                }
                selected[i] = false;
            }
        }
        map.put(symbol, false);
        return false;
    }

    public int format(boolean[] selected) {
        int symbol = 0;
        for (boolean select : selected) {
            symbol <<= 1;
            if (select) {
                symbol |= 1;
            }
        }
        return symbol;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode310. Minimum Height Trees

    在无向图的生成树中,我们可以指定任何一个节点为这棵树的根节点。现在要求在这样一棵生成树中,找到生成树的高度最低的所有根节点。

    眯眯眼的猫头鹰
  • leetcode373. Find K Pairs with Smallest Sums

    两个单调递增的整数数组,现分别从数组1和数组2中取一个数字构成数对,求找到k个和最小的数对。

    眯眯眼的猫头鹰
  • leetcode540. Single Element in a Sorted Array

    You are given a sorted array consisting of only integers where every element app...

    眯眯眼的猫头鹰
  • 使用粒子群优化器来解决旅行商人问题

    粒子群优化器,作为一种使用人工智能来解决问题的方式,在解多元、恒变的方程式方面有很大的优势。在本文中我们主要讲的是通过修改算法来解决一些问题,例如使用离散固定值...

    KX_WEN
  • HDUOJ ----1709

    The Balance Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

    Gxjun
  • HDUOJ--Bone Collector

    Bone Collector Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

    Gxjun
  • HDUOJ----2647Reward

    Reward Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

    Gxjun
  • 使用 Keras搭建一个深度卷积神经网络来识别 c验证码

    本文会通过 Keras 搭建一个深度卷积神经网络来识别验证码,建议使用显卡来运行该项目。

    机器学习AI算法工程
  • JAVA CDI 学习(1) - @Inject基本用法

    CDI(Contexts and Dependency Injection 上下文依赖注入),是JAVA官方提供的依赖注入实现,可用于Dynamic Web M...

    菩提树下的杨过
  • WebRTC基本概念

    STUN(Simple Traversal of UDP Through NATs)其作用是进行 NAT 类型判定,对于可以穿越的 NAT 类型进行UDP穿越。

    音视频_李超

扫码关注云+社区

领取腾讯云代金券