260. 只出现一次的数字 III（位运算）

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for x in nums:
            xor ^= x
        bit = 1
        while (xor & bit) == 0:
            bit <<= 1
        a,b = 0,0
        for i in nums:
            if (i&bit) == 0:
                a ^= i
            else:
                b ^= i
        return [a,b]

474. 一和零（这里用字典做的，如果用二位数组时间复杂度会更高）

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dict1 = {(m,n):0}
        dict2 = {}
        for s in strs:
            count_0 = s.count('0')
            count_1 = s.count('1')
            for k in dict1:
                if k in dict2:
                    dict2[k] = max(dict1[k],dict2[k])
                else:
                    dict2[k] = dict1[k]
                if k[0] >= count_0 and k[1] >= count_1:
                    k2 = (k[0]-count_0,k[1]-count_1)
                    if k2 in dict2:
                        dict2[k2] = max(dict2[k2],dict1[k]+1)
                    else:
                        dict2[k2] = dict1[k] + 1
            dict1 = dict2
            dict2 = {}
        return max(dict1.values())

486. 预测赢家

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        if n%2==0:return True
        dp = [[0]*n for i in range(n)]
        for i in range(n):
            dp[i][i]=nums[i]
        for l in range(1,n):
            for i in range(n):
                j = i+l
                if j<n:
                    dp[i][j] = max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
        return dp[0][n-1]>=0