# # Leetcode 第255场周赛题解

## # Problem A - 找出数组的最大公约数 (opens new window)

### # 方法一：模拟

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

1
2
3

## # Problem B - 找出不同的二进制字符串 (opens new window)

### # 方法一：构造

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
return ''.join(str(1 - int(nums[i][i])) for i in range(len(nums)))

1
2
3

## # Problem C - 最小化目标值与所选元素的差 (opens new window)

### # 方法一：动态规划

• 时间复杂度$\mathcal{O}(N^2ML)$，其中$L=70$
• 空间复杂度$\mathcal{O}(NL)$

class Solution {
public:
int minimizeTheDifference(vector<vector<int>>& mat, int target) {
int n = mat.size(), m = mat[0].size();
int lim = n * 70;
vector<bool> can(lim + 1);
can[0] = true;
for (int i = 0; i < n; ++i) {
vector<bool> ncan(lim + 1);
for (int j = i * 1; j <= i * 70; ++j)
if (can[j])
for (int k = 0; k < m; ++k)
ncan[j + mat[i][k]] = true;
can = move(ncan);
}
int ans = INT_MAX;
for (int i = 0; i <= lim; ++i)
if (can[i])
ans = min(ans, abs(i - target));
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

## # Problem D - 从子集的和还原数组 (opens new window)

### # 方法一：深度优先搜索

1. 所有正数加上一个最大的负数（也就是绝对值最小的负数）
2. 除去最小正数之外的所有正数

• 时间复杂度$\mathcal{O}(N\cdot2^N)$
• 空间复杂度$\mathcal{O}(2^N)$

class Solution:
def recoverArray(self, n: int, sums: List[int]) -> List[int]:
if n == 1:
if 0 not in sums:
return []
return [sum(sums)]

sums.sort()
cnt = collections.Counter(sums)
keys = sorted(cnt.keys())
x = sums[-1] - sums[-2]

# Check x
cnt2 = cnt.copy()
valid = True
rem = []
for key in keys:
if cnt2[key] > 0:
if x == 0:
if cnt2[key] % 2 != 0:
valid = False
break
else:
rem += [key] * (cnt2[key] // 2)
else:
if cnt2[key + x] < cnt2[key]:
valid = False
break
else:
cnt2[key + x] -= cnt2[key]
rem += [key] * cnt2[key]
if valid:
nxt = self.recoverArray(n - 1, rem)
if len(nxt) == n - 1:
return nxt + [x]

# Check -x
if x > 0:
cnt2 = cnt.copy()
valid = True
rem = []
for key in keys[::-1]:
if cnt2[key] > 0:
if cnt2[key - x] < cnt2[key]:
valid = False
break
else:
cnt2[key - x] -= cnt2[key]
rem += [key] * cnt2[key]
if valid:
nxt = self.recoverArray(n - 1, rem)
if len(nxt) == n - 1:
return nxt + [-x]

return []

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55