[leetcode] 464. Can I Win

Description

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. 首先來看如果給定的數字範圍大于等于目标值的話，直接傳回true。
2. 如果給定的數字總和小于目标值的話，說明誰也沒法赢，傳回false。
3. 遞歸函數：首先我們查找目前情況是否在哈希表中存在，有的話直接傳回即可。我們使用一個整型數按位來記錄數組中的某個數字是否使用過，我們周遊所有數字，将該數字對應的mask算出來，如果其和used相與為0的話，說明該數字沒有使用過，我們看如果此時的目标值小于等于目前數字，說明已經赢了，或者我們調用遞歸函數，如果傳回false，說明也是第一個人赢了。（因為目前我們已經選過數字了，此時就該對第二個人調用遞歸函數，隻有他的結果是false，我們才能赢，是以此時我們标記true，傳回true。）
4. 如果周遊完所有數字，我們标記false，傳回false

• 代碼參考了高手的實作，我是寫不出來，學習一下。

代碼

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger>desiredTotal){
            return true;
        }
        int sum=maxChoosableInteger*(maxChoosableInteger+1)/2;
        if(sum<desiredTotal){
            return false;
        }
        unordered_map<int,bool> mp;
        return canWin(maxChoosableInteger,desiredTotal,0,mp);
    }
    
    bool canWin(int length,int total,int used,unordered_map<int, bool>& mp){
        if(mp.count(used)) return mp[used];
        for(int i=0;i<length;i++){
            int cur=(1<<i);
            if((cur&used)==0){
                if(total<=i+1||!canWin(length,total-(i+1),cur|used,mp)){
                    mp[used]=true;
                    return true;
                }
            }
        }
        mp[used]=false;
        return false;
    }
};      

參考文獻