# # Leetcode 第43场双周赛题解

## # Problem A - 计算力扣银行的钱 (opens new window)

### # 方法一：模拟

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

class Solution:
def totalMoney(self, n: int) -> int:
num = [1] * n
ans = 1
for i in range(1, n):
if i % 7 == 0:
num[i] = num[i - 7] + 1
else:
num[i] = num[i - 1] + 1
ans += num[i]
return ans

1
2
3
4
5
6
7
8
9
10
11

### # 方法二：数学

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

class Solution {
fun totalMoney(n: Int): Int {
val fullWeeks = n / 7;
val startOfLastWeek = fullWeeks + 1;
val daysOfLastWeek = n % 7;
return (49 + 7 * fullWeeks) * fullWeeks / 2 + (startOfLastWeek * 2 + daysOfLastWeek - 1) * daysOfLastWeek / 2;
}
}

1
2
3
4
5
6
7
8

## # Problem B - 删除子字符串的最大得分 (opens new window)

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

var maximumGain = function(s, x, y) {
const a = s.split('').map(c => {
if (x > y || (c != 'a' && c != 'b'))
return c;
return c == 'a' ? 'b' : 'a';
});
if (x < y) {
const tmp = x;
x = y;
y = tmp;
}
let ans = 0, na = 0, nb = 0;
for (let c of a) {
if (c != 'a' && c != 'b') {
ans += Math.min(na, nb) * y;
na = 0;
nb = 0;
} else if (c == 'a') {
na++;
} else {
if (na > 0) {
na--;
ans += x;
} else {
nb++;
}
}
}
ans += Math.min(na, nb) * y;
return ans;
};

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

## # Problem C - 构建字典序最大的可行序列 (opens new window)

class Solution {
bool ok;

void rec(vector<int> &ans, set<int, greater<>> &s, int i) {
if (i == ans.size()) {
ok = true;
return;
}
if (ok)
return;
if (ans[i])
rec(ans, s, i + 1);
vector<int> v(s.begin(), s.end());
for (int vi : v) {
if (vi != 1 && (i + vi >= ans.size() || ans[i + vi]))
continue;
ans[i] = vi;
if (vi != 1)
ans[i + vi] = vi;
s.erase(vi);
int idx = i + 1;
while (idx < ans.size() && ans[idx])
idx++;
rec(ans, s, idx);
if (ok)
return;
ans[i] = 0;
if (vi != 1)
ans[i + vi] = 0;
s.insert(vi);
}
}
public:
vector<int> constructDistancedSequence(int n) {
vector<int> ans(n * 2 - 1);
set<int, greater<>> s;
for (int i = 1; i <= n; ++i)
s.insert(i);
ok = false;
rec(ans, s, 0);
return ans;
}
};

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

class Solution:
def solve(self, pos):
if pos == len(self.ans):
self.found = True
if self.found:
return
for i in range(self.n, 0, -1):
if self.used[i] or (i > 1 and (pos + i >= len(self.ans) or self.ans[pos + i] != 0)):
continue
self.used[i] = True
self.ans[pos] = i
if i > 1:
self.ans[pos + i] = i
idx = pos + 1
while idx < len(self.ans) and self.ans[idx] != 0:
idx += 1
self.solve(idx)
if self.found:
return
self.used[i] = False
self.ans[pos] = 0
if i > 1:
self.ans[pos + i] = 0

def constructDistancedSequence(self, n: int) -> List[int]:
self.found = False
self.n = n
self.ans = [0] * (2 * n - 1)
self.used = [False] * (n + 1)
self.solve(0)
return self.ans

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

## # Problem D - 重构一棵树的方案数 (opens new window)

### # 方法一：并查集+拓扑排序

• 利用并查集判断连通性，如果不连通，显然无解
• 遍历三元组，如果三元组构成的三个二元对只出现了两次，则可以确定出这三个数中哪一个应该作为根。
• 遍历二元组，如果该二元组出现了，但是两个数的关系未确定，则可能出现多解。
• 拓扑排序，判断是否有解。如果有解，再根据上一步结果判断是否多解。

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];
}
}
}
};

int in[501];

void init(int idx) {
for (int i = 0; i < idx; ++i)
for (int j = 0; j < idx; ++j)
d[i][j] = adj[i][j] = false;
for (int i = 0; i < idx; ++i)
in[i] = 0;
}

class Solution {
public:
int checkWays(vector<vector<int>>& pairs) {
set<int> s;
for (auto &v : pairs) {
s.insert(v[0]);
s.insert(v[1]);
}
unordered_map<int, int> mp;
int idx = 0;
for (int si : s)
mp[si] = idx++;

UnionFind uf(idx);
init(idx);

for (auto &v : pairs) {
int p = mp[v[0]], q = mp[v[1]];
uf.connect(p, q);
d[p][q] = d[q][p] = true;
}
if (uf.size[uf.find(0)] != idx)
return 0;

for (auto &v : pairs) {
int i = mp[v[0]], j = mp[v[1]];
for (int k = 0; k < idx; ++k) {
if (k == i || k == j)
continue;
int tot = 1 + d[i][k] + d[j][k];
if (tot != 2)
continue;
if (d[i][k]) {
in[j]++;
}
in[k]++;
}
} else {
in[i]++;
}
in[k]++;
}
}
}
}

bool large = false;
for (int i = 0; i < idx && !large; ++i)
for (int j = i + 1; j < idx && !large; ++j)
large = true;

queue<int> q;
for (int i = 0; i < idx; ++i)
if (!in[i])
q.emplace(i);

vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.emplace_back(u);
for (int v = 0; v < idx; ++v) {
if (!--in[v])
q.emplace(v);
}
}
}

if (order.size() != idx)
return 0;

return large ? 2 : 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127