# # Leetcode 第250场周赛题解

## # Problem A - 可以输入的最大单词数 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(|S|)$

• 空间复杂度$\mathcal{O}(|S|)$

class Solution:
def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
words = text.split()
broken = set(brokenLetters)
ans = 0
for word in words:
can = True
for ch in word:
if ch in broken:
can = False
break
if can:
ans += 1
return ans

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

## # Problem B - 新增的最少台阶数 (opens new window)

### # 方法一：贪心

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

class Solution {
public:
int addRungs(vector<int>& rungs, int dist) {
int now = 0, ans = 0;
for (int rung : rungs) {
ans += (rung - now - 1) / dist;
now = rung;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11

## # Problem C - 扣分后的最大得分 (opens new window)

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

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

class Solution {
public:
long long maxPoints(vector<vector<int>>& points) {
int n = points.size(), m = points[0].size();
vector<long long> dp(m);
for (int i = 0; i < n; ++i) {
vector<long long> ndp(m);
long long lmax = 0;
for (int j = 0; j < m; ++j) {
lmax = max(lmax - 1, dp[j]);
ndp[j] = max(ndp[j], lmax);
}
long long rmax = 0;
for (int j = m - 1; j >= 0; --j) {
rmax = max(rmax - 1, dp[j]);
ndp[j] = max(ndp[j], rmax);
}
for (int j = 0; j < m; ++j)
ndp[j] += points[i][j];
dp = move(ndp);
}
return *max_element(dp.begin(), dp.end());
}
};

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

## # Problem D - 查询最大基因差 (opens new window)

### # 方法一：0-1字典树+离线查询

• 时间复杂度$\mathcal{O}((N+Q)K)$。其中$K$为考虑的二进制位数。
• 空间复杂度$\mathcal{O}(N+Q+2^K)$

const int K = 20;

struct TrieNode {
int cnt = 0;
TrieNode *children[2]{};
};

void dfs(int u, vector<vector<int>> &adj, vector<vector<pair<int, int>>> &groups, TrieNode *trie, vector<int> &ans) {
TrieNode *p = trie;
for (int k = K - 1; k >= 0; --k) {
int nxt = (u & (1 << k)) ? 1 : 0;
if (!p->children[nxt])
p->children[nxt] = new TrieNode();
p = p->children[nxt];
p->cnt++;
}

for (auto [val, idx] : groups[u]) {
p = trie;
int hi = 0;
for (int k = K - 1; k >= 0; --k) {
int nxt = (val & (1 << k)) ? 0 : 1;
if (p->children[nxt] && p->children[nxt]->cnt) {
p = p->children[nxt];
hi ^= (1 << k);
} else {
if (!p->children[nxt ^ 1])
p->children[nxt ^ 1] = new TrieNode();
p = p->children[nxt ^ 1];
}
}
ans[idx] = hi;
}

for (int v : adj[u]) {
}

p = trie;
for (int k = K - 1; k >= 0; --k) {
int nxt = (u & (1 << k)) ? 1 : 0;
p = p->children[nxt];
p->cnt--;
}
}

class Solution {
public:
vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
int root = -1;
int n = parents.size();
for (int i = 0; i < n; ++i) {
if (parents[i] == -1)
root = i;
else
}

assert(root != -1);

int q = queries.size();
vector<int> ans(q);
vector<vector<pair<int, int>>> groups(n);
for (int i = 0; i < q; ++i) {
int node = queries[i][0], val = queries[i][1];
groups[node].emplace_back(val, i);
}
TrieNode *trie = new TrieNode();

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