Python solution without using substring

  • 2
    class Solution(object):
        def canWin(self, maxChoosableInteger, desiredTotal, cur, d):
            if cur in d: return d[cur]
            if desiredTotal <= 0:
                d[cur] = False
                return d[cur]
            for i in range(maxChoosableInteger):
                if (cur >> i) & 1 == 0:
                    if not self.canWin(maxChoosableInteger, desiredTotal - (i+1), cur + (1 << i), d):
                        d[cur] = True
                        return d[cur]
            d[cur] = False
            return d[cur]
        def canIWin(self, maxChoosableInteger, desiredTotal):
            if desiredTotal <= 0: return True
            if (maxChoosableInteger+1)*maxChoosableInteger/2 < desiredTotal: return False
            return self.canWin(maxChoosableInteger, desiredTotal, 0, {})

Log in to reply

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