Leetcode-can i win

发布时间:2017-1-20 17:52:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode-can i win ",主要涉及到Leetcode-can i win 方面的内容,对于Leetcode-can i win 感兴趣的同学可以参考一下。

Leetcode-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.


Input:maxChoosableInteger = 10desiredTotal = 11Output:falseExplanation: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.




可以利用穷举所有的选择方案,总共2^maxChoosableInteger 中方式。



在choosenNumberSeq中,用bitmap的方式表示已经选择的数字,比如 choosenNumberSeq=3 那么表示 i=1,2 这两个数字已经被选择了。

在实现的过程中,还可以考虑通过存储中间的计算过程来减少递归过程中带来的重复计算,比如 winState数组。

 private Boolean[] winState;    int choosenNumberSeq = 0;    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {        if (desiredTotal == 0) {            return true;        }        //it shows that we add all of them but can't get desiredTotal        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {            return false;        }        winState = new Boolean[1 << maxChoosableInteger]; // about 2^( maxChoosableInteger) options to choose        return canWin(maxChoosableInteger, desiredTotal, 0);    }    private boolean canWin(int maxChoosableInteger, int desiredTotal, int sumNow) {        if (winState[choosenNumberSeq] != null)  //this shows that it has calculated this result before            return winState[choosenNumberSeq];        if (sumNow >= desiredTotal) {       //this shows that in this state ,i lost            winState[choosenNumberSeq] = false;            return false;        }        for (int i = 1; i <= maxChoosableInteger; i++) {            int bit = 1 << (i - 1);            if ((choosenNumberSeq & bit) == 0) { //number (i) never be chosen before                choosenNumberSeq ^= bit;                boolean ulose = !canWin(maxChoosableInteger, desiredTotal, sumNow + i);                choosenNumberSeq ^= bit;                if (ulose) {   //this shows that in this state opponent will fail ,it worths  to choosing it                    winState[choosenNumberSeq] = true;                    return true;                }            }        }        winState[choosenNumberSeq] = false;        return false;    }