# Leetcode 第218场周赛题解

# Problem A - 设计 Goal 解析器 (opens new window)

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

class Solution {
public:
string interpret(string command) {
string ans;
for (int i = 0; i < command.size(); ++i) {
char c = command[i];
if (c == 'G')
ans.push_back(c);
else if (c == '(') {
if (command[i + 1] == ')')
ans.push_back('o'), i++;
else
ans += "al", i += 3;
}
}
return ans;
}
};

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

# Problem B - K 和数对的最大数目 (opens new window)

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

class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
int ans = 0;
unordered_map<int, int> mp;
for (int num : nums)
mp[num]++;
for (auto [num, freq] : mp) {
if (num * 2 == k) {
ans += freq / 2;
} else if (mp.count(k - num)) {
int delta = min(freq, mp[k - num]);
mp[k - num] -= delta;
mp[num] -= delta;
ans += delta;
}
}
return ans;
}
};

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

# Problem C - 连接连续二进制数字 (opens new window)

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

mod = 1000000007

class Solution:
def concatenatedBinary(self, n: int) -> int:
ans = 0
for i in range(1, n + 1):
b = bin(i)[2:]
n = len(b)
ans = ans * pow(2, n) % mod
ans = (ans + i) % mod
return ans

1
2
3
4
5
6
7
8
9
10
11

const int MOD = 1e9 + 7;

class Solution {
public:
int concatenatedBinary(int n) {
long long ans = 0;
for (int i = 1; i <= n; ++i) {
int len = 32 - __builtin_clz(i);
ans = ((ans << len) + i) % MOD;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# Problem D - 最小不兼容性 (opens new window)

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

// 优化四：指令集优化，让CPU使用POPCNT指令，从而加速__builtin_popcount
#pragma GCC target ("sse4.2")

const int INF = 0x3f3f3f3f;
int memo[65536], v[16];

class Solution {
int n, k, sz;
vector<int> nums;
int solve(int state) {
if (memo[state] != -1)
return memo[state];

// 边界条件：当前集合刚好包含n/k个元素，不需要继续划分
if (__builtin_popcount(state) == sz) {
int idx = 0;
for (int i = 0; i < n; ++i)
if (state & (1 << i))
v[idx++] = i;
for (int i = 0; i + 1 < sz; ++i)
if (nums[v[i]] == nums[v[i + 1]])
return memo[state] = INF;
return memo[state] = nums[v[n / k - 1]] - nums[v[0]];
}
int ans = INF;

// 优化二：子集枚举优化
for (int sub = state & (state - 1); sub; sub = (sub - 1) & state) {
if (__builtin_popcount(sub) % sz != 0)
continue;
int left = solve(sub);

// 优化三：如果左边的最优值已经达到了当前总和的最优值，则不需要继续计算右边。
if (left >= ans)
continue;
int right = solve(state ^ sub);
ans = min(ans, left + right);
}
return memo[state] = ans;
}

public:
int minimumIncompatibility(vector<int>& nums, int k) {
n = nums.size();
this->k = k;
sz = n / k;

// 优化一：每个子集的大小为1，不兼容性显然为0，总和也是0。
// 这种情况的筛除非常重要，因为它需要最多的枚举次数。
if (sz == 1)
return 0;

sort(nums.begin(), nums.end());
vector<int> cnt(n + 1);
for (int num : nums) {
cnt[num]++;
if (cnt[num] > k)
return -1;
}
this->nums = nums;
for (int i = 0; i < (1 << n); ++i)
memo[i] = -1;
return solve((1 << n) - 1);
}
};

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
56
57
58
59
60
61
62
63
64
65