周赛笔记255

一、找出数组的最大公约数

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        a, b = min(nums), max(nums)
        return math.gcd(a,b)

二、找出不同的二进制字符串

特例处理 + 状态压缩的方法:

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        
        n = len(nums)
        
        if n==1:
            return "1" if "0" in nums else "0"
        
        if n==2 and nums==["10","11"]:
            return "00"
        
        mask = (1<<(n-1))
        for v in range(n):
            mask_v = bin(mask | (1<<v))[2:]
            if mask_v not in nums:
                return mask_v

不知道为啥这会超时：

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:   
        n = len(nums)
        nums = set(nums)

        def fun(n,s):
            if n==0: yield s
            yield from fun(n-1,"0"+s)
            yield from fun(n-1,"1"+s)

        for num in fun(n,""):
            if num not in nums:
                return num

三、最小化目标值与所选元素的差

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        rows, cols = len(mat), len(mat[0])
        arr = set(mat[0])
        for i in range(1, rows):
            arr = set(pre+suf for pre in arr for suf in mat[i])
        
        arr = list(arr)
        arr.sort()
        idx = bisect.bisect_left(arr,target)
        #print(arr,idx)
        
        if idx == len(arr):
            return abs(arr[idx-1]-target)
        
        if idx == 0:
            return abs(arr[idx]-target)
        
        return min(abs(arr[idx]-target),abs(arr[idx-1]-target))

#侥幸过了...
#看他们也是暴力过的...

四、从子集的和还原数组

class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        ans = []
        sums.sort(reverse = True)

        while len(sums) > 1:
            a, b = sums[:1]

            x = a-b # 最大元素
            tmp = [] # 和不包含x的元素
            d = defaultdict(int)
            for num in sums:
                if num in d and d[num] > 0:
                    d[num] -= 1
                else:
                    q = num - x
                    tmp.append(q)
                    d[q] += 1
            if 0 in tmp:
                sums = tmp
                ans.append(x)
                continue

            x = b-a
            ans.append(x)
            tmp = []
            d = defaultdict(int)
            for num in sums:
                if num in d and d[num] > 0:
                    d[num] -= 1
                else:
                    tmp.append(num)
                    q = num + x
                    d[q] += 1
            sums = tmp
        return ans

copy，不懂，应该是数学题