C++ easy understood 269ms solution with comments


  • 4
    W
    class Solution {
        unordered_map<unsigned int,bool> cache;
    public:
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(maxChoosableInteger>=desiredTotal) return true;
            //the sum of all available numbers are less than desireTotal, which means it cannot reach the desireTotal
            if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
            unsigned int used = (1<<maxChoosableInteger)-1; // use bit to record which number has been used (bit '1' means available, bit '0' means used)
            return play(desiredTotal,used,maxChoosableInteger);
        }
        bool play(int target, unsigned int used, int size){
            if(cache.find(used) != cache.end()) return cache[used];
            //exist available integer >= target, return true
            if(target-1<size && (used > (1<<target-1))){
                cache[used] = true;
                return true;
            }
            int bit = 1;
            for(int i = 0; i<size; i++,bit <<=1){
                if((used & bit)== 0) continue; // the (i+1)th bit is '0', means (i+1) is used
                used ^= bit;
                if(!play(target-i-1,used,size)){
                    used |= bit;
                    cache[used] = true;
                    return true;
                }
                used |= bit;
            }
            cache[used] =  false;
            return false;
        }
    };
    

  • 0
    This post is deleted!

  • 0
    S

    desiredTotal should also be stored as part of cache. Basically map bits+desiredTotal to a bool value. Since maxChoosableInteger is not bigger than 20, we can use rest bits (high 12 bits for example) to store desiredTotal


  • 0
    C

    @songruibin Actually desiredTotal is a function of bits. So it's not needed in the cache.


  • 0
    L

    Why did you use unsigned int instead of int?


  • 0
    B

    a little change to make it more clear.
    And @songruibin At first, I have the same question as you, so I use dp[2^20][300], then I realize
    for a certain desiredTotal, each used correspond to a desired num(desiredTotal - the number has been used) so we don't need to store the desiredTotal in cache.
    However, if we want to get the result for more than once, store the desiredTotal in cache will reduce repeated calculation.

        unordered_map<int, bool> cache;
    	bool winThis(int canUse, int d) {
    		if (d <= 0) return false;
    		if (cache.find(canUse) != cache.end()) return cache[canUse];
    		int bit = 1;
    		int cnt = 1;
    		while (bit<=canUse)
    		{
    			if (bit&canUse&&!winThis(canUse^bit,d-cnt)) {
    				cache[canUse] = true;
    				return true;
    			}
    			cnt++;
    			bit <<= 1;
    		}
    		return cache[canUse] = false;
    	}
    
    	bool canIWin(int maxChoosableInteger, int desiredTotal) {
    		if (desiredTotal > (1 + maxChoosableInteger)*maxChoosableInteger / 2) return false;
    		if (maxChoosableInteger>=desiredTotal) return true;
    		return winThis((1<<maxChoosableInteger)-1, desiredTotal);
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.