# # Leetcode 第221场周赛题解

## # Problem A - 判断字符串的两半是否相似 (opens new window)

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

class Solution:
def halvesAreAlike(self, s: str) -> bool:
vowels = set(list('aeiouAEIOU'))
l = 0
r = 0
n = len(s)
for c in s[:n // 2]:
if c in vowels:
l += 1
for c in s[n // 2:]:
if c in vowels:
r += 1
return l == r

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

## # Problem B - 吃苹果的最大数目 (opens new window)

• 时间复杂度$\mathcal{O}(\max(i+days[i])\cdot\log N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
int eatenApples(vector<int>& apples, vector<int>& days) {
map<int, int> cnt;
int ans = 0;
int n = apples.size();
auto add = [&](int i) {
if (apples[i])
cnt[i + days[i]] += apples[i];
};
auto eat = [&](int i) {
while (!cnt.empty() && cnt.begin()->first <= i)
cnt.erase(cnt.begin());
if (!cnt.empty()) {
ans++;
int d = cnt.begin()->first;
cnt[d]--;
if (cnt[d] == 0)
cnt.erase(cnt.begin());
}
};
for (int i = 0; i < n; ++i) {
add(i);
eat(i);
}
for (int i = n; !cnt.empty(); ++i)
eat(i);
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

## # Problem C - 球会落何处 (opens new window)

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

class Solution {
public:
vector<int> findBall(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<int> ans(m);
for (int i = 0; i < m; ++i) {
int col = i;
for (int j = 0; j < n; ++j) {
if (grid[j][col] == 1 && col + 1 < m && grid[j][col + 1] == 1) {
col++;
} else if (grid[j][col] == -1 && col > 0 && grid[j][col - 1] == -1) {
col--;
} else {
ans[i] = -1;
break;
}
}
if (ans[i] != -1)
ans[i] = col;
}
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

## # Problem D - 与数组中元素的最大异或值 (opens new window)

• 如果$x_i$的当前位为$1$，我们应当优先走当前位为$0$的分支；否则，我们尝试走当前位为$1$的分支，如果分支不存在，或分支的最小元素也超过了$m_i$，则本查询无解。
• 如果$x_i$的当前位为$0$，我们应当优先走当前位为$1$的分支，但要求这一分支的最小元素不超过$m_i$；否则，我们尝试走当前位为$0$的分支。

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

struct TrieNode {
int lo = INT_MAX;
TrieNode* children[2]{};
};

class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
TrieNode* root = new TrieNode();
for (int num : nums) {
TrieNode* p = root;
for (int i = 30; i >= 0; --i) {
int nxt = (num & (1 << i)) ? 1 : 0;
if (!p->children[nxt]) p->children[nxt] = new TrieNode();
p = p->children[nxt];
p->lo = min(p->lo, num);
}
}
vector<int> ret;
for (auto q : queries) {
int x = q[0], limit = q[1];
int ans = 0;
TrieNode* p = root;
for (int i = 30; i >= 0; --i) {
if (x & (1 << i)) {
if (p->children[0]) {
p = p->children[0];
ans ^= (1 << i);
} else if (!p->children[1] || (p->children[1]->lo > limit)) {
ret.emplace_back(-1);
break;
} else {
p = p->children[1];
}
} else {
if (p->children[1] && (p->children[1]->lo <= limit)) {
p = p->children[1];
ans ^= (1 << i);
} else if (!p->children[0]) {
ret.emplace_back(-1);
break;
} else {
p = p->children[0];
}
}
if (i == 0) ret.emplace_back(ans);
}
}
return ret;
}
};

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