C++ bitset easy to understand


  • 0
    A
    class Solution {
    	bool helper(bitset<32>& mask, int m, int ps, int tgt, unordered_map<unsigned long, bool>& memo) {
    		if (mask.count() == m ) return false;
    		if (memo.count(mask.to_ulong()) > 0)
    			return memo[mask.to_ulong()];
    		for (int i = 0; i < m; i++) {
    			if (!mask.test(i)) {
    				bitset<32> tm = mask;
    				tm.set(i, 1);
    				unsigned long t = tm.to_ulong();
    				if (ps + i + 1 >= tgt || !helper(tm, m, ps + i + 1, tgt, memo)) {
    					memo[mask.to_ulong()] = true;
    					return true;
    				}
    			}
    		}
    		memo[mask.to_ulong()] = false;
    		return false;
    	}
    public:
    	bool canIWin(int m, int d) {
    		if( m * ( m + 1)/2 < d)
    			return false;
    
    		bitset<32> mask(0);
    		unordered_map<unsigned long, bool> memo;
    		return helper(mask, m, 0, d, memo);
    	}
    };
    

Log in to reply
 

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