Leetcode-can i win

发布时间:2017-3-26 1:34:08 编辑: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.

Example

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;    }

上一篇:qt检测网络连接状态【只能检测和路由器的连接,不能测试到外网的连接】
下一篇:数据库imp导表dmp的方法

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款