Python DFS w/ memorization & bit manipulation


  • 0
    class Solution(object):
        def canIWin(self, maxChoosableInteger, desiredTotal):
            """
            :type maxChoosableInteger: int
            :type desiredTotal: int
            :rtype: bool
            """
            def helper(pool, target, visited):
                if pool in visited:
                    return visited[pool]
                if target <= 0:
                    return False
                    
                mask = 0x01
                for i in xrange(0, maxChoosableInteger):
                    if pool & mask == 0:
                        if helper(pool | mask, target - (i + 1), visited) == False:
                            visited[pool] = True
                            return True
                    mask = mask << 1
                visited[pool] = False
                return False
    
            if (1 + maxChoosableInteger) * (maxChoosableInteger / 2) < desiredTotal:
                return False
            if desiredTotal == 0:
                return True
            pool = 0
            visited = {}
            return helper(pool, desiredTotal, visited)
    

Log in to reply
 

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