# Leetcode 第223场周赛题解

# Problem A - 解码异或后的数组 (opens new window)

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

class Solution {
public:
vector<int> decode(vector<int>& encoded, int first) {
int n = encoded.size() + 1;
vector<int> ans(n);
ans[0] = first;
for (int i = 1; i < n; ++i)
ans[i] = ans[i - 1] ^ encoded[i - 1];
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11

# Problem B - 交换链表中的节点 (opens new window)

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

class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
int len = 0;
while (ptr) {
len++;
ptr = ptr->next;
}
auto get_node = [&](int idx) {
for (int i = 0; i < idx - 1; ++i)
ptr = ptr->next;
return ptr;
};
auto left = get_node(k);
auto right = get_node(len + 1 - k);
swap(left->val, right->val);
}
};

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

# Problem C - 执行交换操作后的最小汉明距离 (opens new window)

• 时间复杂度$\mathcal{O}(N+M)$，其中$N$$target$$source$的长度，$M$$allowedSwaps$的长度。
• 空间复杂度$\mathcal{O}(N)$

struct UnionFind {
int n;
vector<int> parent, size;
UnionFind(int n) {
this->n = n;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
} else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}
};

class Solution {
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
int n = source.size();
UnionFind uf(n);
for (auto &v : allowedSwaps)
uf.connect(v[0], v[1]);
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; ++i)
groups[uf.find(i)].emplace_back(i);
int same = 0;
for (auto [root, group] : groups) {
unordered_map<int, int> sc, tc;
for (int i : group) {
sc[source[i]]++;
tc[target[i]]++;
}
for (auto [num, freq] : tc)
same += min(freq, sc[num]);
}
return n - same;
}
};

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

# Problem D - 完成所有工作的最短时间 (opens new window)

• 时间复杂度$\mathcal{O}(3^N\log\sum job_i))$，其中$N$是任务的数量。
• 空间复杂度$\mathcal{O}(2^N)$

class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
int lo = *max_element(jobs.begin(), jobs.end());
int hi = 0;
for (int job : jobs)
hi += job;
vector<int> subsum(1 << n);
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j)
if (i & (1 << j))
subsum[i] += jobs[j];
}
auto can = [&](int limit) {
vector<int> dp(1 << n, 1e9);
dp[0] = 0;
for (int i = 0; i < (1 << n); ++i) {
int rem = ((1 << n) - 1) ^ i;
for (int j = rem; j; j = (j - 1) & rem)
if (subsum[j] <= limit)
dp[i ^ j] = min(dp[i ^ j], dp[i] + 1);
}
return dp[(1 << n) - 1] <= k;
};
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (can(mid))
hi = mid - 1;
else
lo = mid + 1;
}
return lo;
}
};

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

# 优化一 动态规划的优化

• 时间复杂度$\mathcal{O}(N\cdot2^N\log\sum job_i))$，其中$N$是任务的数量。
• 空间复杂度$\mathcal{O}(2^N)$

class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
int lo = *max_element(jobs.begin(), jobs.end());
int hi = 0;
for (int job : jobs)
hi += job;
int mask = 1 << n;
auto can = [&](int limit) {
vector<pair<int, int>> dp(mask, make_pair(k + 1, 0));
dp[0] = {0, limit};
for (int i = 0; i < mask; ++i) {
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
continue;
pair<int, int> nxt = dp[i].second + jobs[j] <= limit ? make_pair(dp[i].first, dp[i].second + jobs[j]) : make_pair(dp[i].first + 1, jobs[j]);
dp[i ^ (1 << j)] = min(dp[i ^ (1 << j)], nxt);
}
}
return dp[mask - 1].first <= k;
};
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (can(mid))
hi = mid - 1;
else
lo = mid + 1;
}
return lo;
}
};

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

# 优化二 二分上下界的优化

• 时间复杂度$\mathcal{O}(N\cdot2^N\log2^N))=\mathcal{O}(N^2\cdot2^N)$，其中$N$是任务的数量。
• 空间复杂度$\mathcal{O}(2^N)$

class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
int mask = 1 << n;
for (int i = 0; i < mask; ++i)
for (int j = 0; j < n; ++j)
if (i & (1 << j))
sub[i] += jobs[j];
set<int> s(sub.begin(), sub.end());
int ma = *max_element(jobs.begin(), jobs.end());
vector<int> v;
for (int i : s)
if (i >= ma)
v.emplace_back(i);
auto can = [&](int limit) {
vector<pair<int, int>> dp(mask, make_pair(k + 1, 0));
dp[0] = {0, limit};
for (int i = 0; i < mask; ++i) {
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
continue;
pair<int, int> nxt = dp[i].second + jobs[j] <= limit ? make_pair(dp[i].first, dp[i].second + jobs[j]) : make_pair(dp[i].first + 1, jobs[j]);
dp[i ^ (1 << j)] = min(dp[i ^ (1 << j)], nxt);
}
}
return dp[mask - 1].first <= k;
};
int lo = 0, hi = v.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (can(v[mid]))
hi = mid - 1;
else
lo = mid + 1;
}
return v[lo];
}
};

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