# # Leetcode 第64场双周赛题解

## # Problem A - 数组中第 K 个独一无二的字符串 (opens new window)

### # 方法一：模拟

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

class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
cnt = collections.Counter(arr)
uniq = [s for s in arr if cnt[s] == 1]
return uniq[k - 1] if len(uniq) >= k else ""

1
2
3
4
5

## # Problem B - 两个最好的不重叠活动 (opens new window)

### # 方法一：排序+优先队列

• 选择此刻已经结束的活动中价值最大的。
• 选择当前活动。

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

class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end());
int ans = 0, hi = 0, n = events.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int i = 0; i < n; ++i) {
int s = events[i][0], e = events[i][1], v = events[i][2];
while (!pq.empty() && pq.top().first < s) {
hi = max(hi, pq.top().second);
pq.pop();
}
ans = max(ans, hi + v);
pq.emplace(e, v);
}
return ans;
}
};

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

## # Problem C - 蜡烛之间的盘子 (opens new window)

### # 方法一：前缀和

• plates[i]代表$[1,i]$中盘子的总数
• rcandle[i]代表$[1,i]$中最靠右的蜡烛的位置
• lcandle[i]代表$[i+1,n]$中最靠左的蜡烛的位置

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

class Solution {
public:
vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
int n = s.size();
vector<int> plates(n + 1), lcandle(n + 1, n + 1), rcandle(n + 1);
for (int i = 1; i <= n; ++i) {
plates[i] = plates[i - 1];
rcandle[i] = rcandle[i - 1];
if (s[i - 1] == '*')
plates[i]++;
else
rcandle[i] = i;
}
for (int i = n - 1; i >= 0; --i) {
lcandle[i] = lcandle[i + 1];
if (s[i] == '|')
lcandle[i] = i + 1;
}

int q = queries.size();
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int l = queries[i][0] + 1, r = queries[i][1] + 1;
int lc = lcandle[l - 1], rc = rcandle[r];
if (lc >= rc)
continue;
ans[i] = plates[rc] - plates[lc];
}

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

## # Problem D - 棋盘上有效移动组合的数目 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(64^N\cdot N^2)$。但由于限制了最多有一个皇后，实际最大的复杂度是$\mathcal{O}(64\cdot 32^{N-1}\cdot N^2)$
• 空间复杂度$\mathcal{O}(N)$

const int d[8][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};

class Solution {
vector<vector<int>> positions, possible;
int n, ans = 0;
vector<int> direction, step, xinit, yinit;

bool valid(int x, int y) {
return x >= 1 && x <= 8 && y >= 1 && y <= 8;
}

void check() {
vector<int> x(xinit), y(yinit), s(step);
bool go = true;
while (go) {
go = false;
for (int i = 0; i < n; ++i) {
if (s[i] > 0) {
s[i]--;
x[i] += d[direction[i]][0];
y[i] += d[direction[i]][1];
}
if (s[i])
go = true;
}
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (x[i] == x[j] && y[i] == y[j])
return;
}
ans++;
}

void dfs(int i) {
if (i == n) {
check();
} else {
direction.push_back(0);
step.push_back(0);
dfs(i + 1);
direction.pop_back();
step.pop_back();

for (int j = 1; j < 8; ++j) {
for (int k : possible[i]) {
int x = positions[i][0] + d[k][0] * j, y = positions[i][1] + d[k][1] * j;
if (valid(x, y)) {
direction.push_back(k);
step.push_back(j);
dfs(i + 1);
direction.pop_back();
step.pop_back();
}
}
}
}
}
public:
int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {
n = pieces.size();
possible = vector<vector<int>>(n);
this->positions = positions;
xinit = vector<int>(n), yinit = vector<int>(n);
for (int i = 0; i < n; ++i) {
xinit[i] = positions[i][0], yinit[i] = positions[i][1];
if (pieces[i] != "rook") {
possible[i].emplace_back(1);
possible[i].emplace_back(3);
possible[i].emplace_back(5);
possible[i].emplace_back(7);
}
if (pieces[i] != "bishop") {
possible[i].emplace_back(0);
possible[i].emplace_back(2);
possible[i].emplace_back(4);
possible[i].emplace_back(6);
}
}

dfs(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
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