Leetcode 周赛题解 221
难度顺序：
。
1704. 判断字符串的两半是否相似
给你一个偶数长度的字符串 s 。将其拆分成长度相同的两半，前一半为 a ，后一半为 b 。
两个字符串 相似 的前提是它们都含有相同数目的元音（'a'，'e'，'i'，'o'，'u'，'A'，'E'，'I'，'O'，'U'）。注意，s 可能同时含有大写和小写字母。
如果 a 和 b 相似，返回 true ；否则，返回 false 。
示例 1：
输入：s = "book"
输出：true
解释：a = "bo" 且 b = "ok" 。a 中有 1 个元音，b 也有 1 个元音。所以，a 和 b 相似。
提示：
2 <= s.length <= 1000s.length是偶数s由 大写和小写 字母组成
思路：
按题意判断前一半元音字母个数和后一半元音字母个数是否相同。
时间复杂度：
.
class Solution {
public:
bool halvesAreAlike(string s) {
int cnt = 0, ret = 0;
string tmp = "aeiou";
int n = s.length() / 2;
for(char c: s) {
for(char d: tmp) {
if(c == d || c == d - 'a' + 'A') {
++ cnt;
c = -1;
}
}
-- n;
if(n == 0) ret = cnt;
}
return cnt == ret * 2;
}
};
1705. 吃苹果的最大数目
有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
示例 1：
输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。
提示：
apples.length == ndays.length == n1 <= n <= 2 * 10^40 <= apples[i], days[i] <= 2 * 10^4- 只有在
apples[i] = 0时，days[i] = 0才成立
思路：
注意到苹果保质期最大只有20000天，所以我们枚举每一天是否有苹果吃即可。
考虑到当前是第
天，对于前
天产生苹果肯定优先吃最快过期的苹果。
所以我们用一个最小堆的结构即可维护这个，可以利用c++自带的set完成。
时间复杂度：
.
class Solution {
public:
struct node {
int ed, num;
//ed 表示苹果截止日期
//num 表示苹果个数
bool operator <(const node &b) const {
return ed < b.ed;
}
};
const int MXN = 4e4 + 5;
int eatenApples(vector<int>& apples, vector<int>& days) {
set<node> st;
int n = apples.size(), cnt = 0;
for(int i = 1; i < MXN; ++i) {
if(i <= n && apples[i - 1] != 0 && days[i - 1] != 0) st.insert(node{i - 1 + days[i - 1], apples[i - 1]});
if(st.empty()) continue;
node p = *st.begin();
st.erase(st.begin());
if(i <= p.ed) {//可以吃苹果就吃
-- p.num;
++ cnt;
if(p.num) st.insert(p);//还有剩的就继续放进去
}
else -- i;//可能set中还有苹果没用到，所以第i天至少还要判断一次
}
return cnt;
}
};
1706. 球会落何处
用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。
- 将球导向右侧的挡板跨过左上角和右下角，在网格中用
1表示。 - 将球导向左侧的挡板跨过右上角和左下角，在网格中用
-1表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。
示例 1：
输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 100grid[i][j]为1或-1
思路
模拟题，记录每个球的行动路径即可。
时间复杂度：
.
class Solution {
public:
vector<int> findBall(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> ans(n, -1);
for(int i = 0; i < n; ++i) {//第i列球
int now = i, flag = 1;//当前在第now列
for(int j = 0; j < m; ++j) {//当前在第j行
if(grid[j][now] == 1) {//向右滑
if(now + 1 == n || grid[j][now + 1] == -1) flag = 0;
++ now;
}else {
if(now == 0 || grid[j][now - 1] == 1) flag = 0;
-- now;
}
if(flag == 0) break;
}
if(flag) ans[i] = now;
}
return ans;
}
};
1707. 与数组中元素的最大异或值
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
提示：
1 <= nums.length, queries.length <= 10^5queries[i].length == 20 <= nums[j], xi, mi <= 10^9
思路
因为要求的是小于等于
的权值与
异或出的最大值。我们利用离线思想将
从小到大排序后，每次将小于等于
的权值插入字典树然后查询即可。
这是一个非常好写的离线做法，如果要在线写的话，就是一个贪心题了，下面介绍在线的贪心做法。
其实我们在走字典树的时候只多了一个条件，就是保证求出来的一定是小于等于
的权值异或出来的贡献。
那么我们字典树每个节点多记录一个权值表示子树内最小的叶子节点的权值，走字典树的时候保证子树内最小权值一定要小于等于
即可，见代码注释。
时间复杂度：
.
const int INF = 0x3f3f3f3f;
const int MXN = 1e5 * 32 + 11;
class Solution {
public:
int trie[MXN][2], siz, Min[MXN];
int newNode() {
++ siz;
trie[siz][0] = trie[siz][1] = -1;
Min[siz] = INF;
return siz;
}
void add(int x) {
int rt = 0;
for(int i = 31; i >= 0; --i) {
Min[rt] = min(Min[rt], x);
int now = (x >> i) & 1;
if(trie[rt][now] == -1) trie[rt][now] = newNode();
rt = trie[rt][now];
}
Min[rt] = x;
}
int check(int x, int m) {
int rt = 0, ans = -1;
for(int i = 31; i >= 0; --i) {
int now = (x >> i) & 1;
int vis[2] = {0, 0};
if(trie[rt][0] != -1 && Min[trie[rt][0]] <= m) vis[0] = 1;
if(trie[rt][1] != -1 && Min[trie[rt][1]] <= m) vis[1] = 1;
if(vis[!now]) {
if(ans == -1) ans = 0;
ans += (1 << i);
rt = trie[rt][!now];
}else if(vis[now]) {
if(ans == -1) ans = 0;
rt = trie[rt][now];
}else {
ans = -1;
break;
}
}
return ans;
}
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size(), m = queries.size();
vector<int> ans(m, -1);
siz = 0;
trie[siz][0] = trie[siz][1] = -1;
Min[siz] = INF;
for(int i = 0; i < n; ++i) add(nums[i]);
for(int i = 0; i < m; ++i) {
ans[i] = check(queries[i][0], queries[i][1]);
}
return ans;
}
};
