[leetcode] 464. Can I Win (Medium)

两个人依次从1~maxNum中选取数字（不可重复选取同一个），累和。当一方选取数字累和后结果大于等于给定的目标数字，则此人胜利。

题目给一个maxNum和targetNum，要求判断先手能否胜利。

思路：

首先判断两种特殊条件：

可选最大值大于等于目标值，直接返回true。
其中一个人可选的最大值小于目标值，直接返回false。

具体再看题目，题目给出maxNum不大于20，则可状态压缩为一个int（32位）来保存每个数字是否被使用过（题解中利用1-32位进行存储）。

利用一个map存储选取每一个数字的情况，每一次选择前进行判断，如若已经有过选取该数字的情况，则返回map里的值。

遍历i从1到maxN，考虑选取i的情况：

判断先手胜利条件：

选上i数字后，大于等于目标值可胜利。( i >= targetN )
选上i数字后，后手输了。( helper(maxN, targetN - i, mask | visited) == false) )

返回true。

其他情况下，则表示先手输，返回false。

Runtime: 137 ms, faster than 43.48% of Java

class Solution {

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

    public boolean helper(int maxN, int targetN, int visited) {

        if (m.containsKey(visited))

            return m.get(visited);

        for (int i = 1; i <= maxN; i++) {

            int mask = (1 << i);

            if ((mask & visited) == 0 && (i >= targetN || helper(maxN, targetN - i, mask | visited) == false)) {

                m.put(visited, true);

                return true;

            }

        }

        m.put(visited, false);

        return false;

    }

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

        if (maxChoosableInteger >= desiredTotal)

            return true;

        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)

            return false;

        return helper(maxChoosableInteger, desiredTotal, 0);

    }

}

巴特西

[leetcode] 464. Can I Win (Medium)

最新文章

热门文章