前言
军服外面加了轻便的装甲。而且，身后还背着大得不甚体面的大剑。 三名少女各自完成了战斗的准备。
「那么，我们要走喽──」 艾瑟雅露出一如往常的笑容挥了挥手。
「……嗯。」 奈芙莲微微点头。
只有珂朵莉一个人不回头，也不说话。只有银色的胸针在她那身军服的胸前幽幽地发着光，似乎正诉说着什么。
就这样，三名妖精起飞出发了。 少女们的背影逐渐溶入夕色中。
整体评价
难得有意思的t2，在周赛评论区，众多大佬也卡了会， t4是道0-1 Trie的经典题。
VP入口： 第 221 场周赛
更多解题报告详见：珂朵莉MM的解题报告汇总
T1. 判断字符串的两半是否相似
如何快速判断字母是元音字母，感觉有个小技巧。
"aeiouAEIOU".indexOf(c) != -1Java
class Solution {
int parse(String s) {
return (int)s.chars().filter(c -> "aeiouAEIOU".indexOf(c) != -1).count();
}
public boolean halvesAreAlike(String s) {
int n = s.length();
return parse(s.substring(0, n / 2)) == parse(s.substring(n / 2));
}
}T2. 吃苹果的最大数目
这题不好解，只能强行模拟，如果往贪心，dp，差分考虑，容易绕进去。
可以借助优先队列，或者类似的数据结构来模拟。
不过这边，珂朵莉选择用java的TreeMap来实现，这边等价于PriorityQueue了
Java
class Solution {
public int eatenApples(int[] apples, int[] days) {
int n = apples.length;
int ans = 0;
TreeMap<Integer, Integer> treap = new TreeMap<>();
for (int i = 0; i < n; i++) {
int tv = i + days[i];
treap.put(tv, treap.getOrDefault(tv, 0) + apples[i]);
// *) 处理过期的
Iterator<Map.Entry<Integer, Integer>> iter = treap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<Integer, Integer> e = iter.next();
if (e.getKey() > i) {
break;
} else {
iter.remove();
}
}
Map.Entry<Integer, Integer> e = treap.ceilingEntry(i);
if (e != null && e.getValue() > 0) {
ans++;
if (e.getValue() == 1) {
treap.remove(e.getKey());
} else {
treap.put(e.getKey(), e.getValue() - 1);
}
}
}
// 这边有个收尾工作，就是超过n天的情况
for (int i = n; !treap.isEmpty(); i++) {
Iterator<Map.Entry<Integer, Integer>> iter = treap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<Integer, Integer> e = iter.next();
if (e.getKey() > i) {
break;
} else {
iter.remove();
}
}
Map.Entry<Integer, Integer> e = treap.ceilingEntry(i);
if (e != null && e.getValue() > 0) {
ans++;
if (e.getValue() == 1) {
treap.remove(e.getKey());
} else {
treap.put(e.getKey(), e.getValue() - 1);
}
}
}
return ans;
}
}最后还是大模拟来求解。
T3. 球会落何处
模拟题，算是比较简单，如果t2和t3，感觉会更好.
就是定义终态，到左右两侧的边，V字结构，底部。
因为每次总往下一步，所以整体的时间复杂度为
Java
class Solution {
public int[] findBall(int[][] grid) {
int r = grid.length;
int c = grid[0].length;
int[] res = new int[c];
for (int i = 0; i < c; i++) {
int y = 0, x = i;
while (true) {
int v = grid[y][x];
if (v == 1) {
if (x == c - 1) {
res[i] = -1;
break;
} else if (grid[y][x + 1] == -1) {
res[i] = -1;
break;
} else {
y++;
x++;
}
} else if (v == -1) {
if (x == 0) {
res[i] = -1;
break;
} else if (grid[y][x - 1] == 1) {
res[i] = -1;
break;
} else {
y++;
x--;
}
}
if (y == r) {
res[i] = x;
break;
}
}
}
return res;
}
}T4. 与数组中元素的最大异或值
求异或值最大，一般用0-1 Trie做快速贪心刷选，不过题意中，额外加了一个限制条件，不过不影响整个代码结构。
Java
class Solution {
static int gBit = 30;
static int gRes = 0;
static class Trie {
Trie[] child = new Trie[2];
boolean tag;
int val;
public static void add(Trie root, int val) {
Trie cur = root;
int acc = 0;
for (int i = gBit; i >= 0; i--) {
int t = (val >> i) & 0x01;
if (cur.child[t] == null) {
cur.child[t] = new Trie();
}
cur = cur.child[t];
acc |= (t << i);
cur.val = acc;
}
cur.tag = true;
cur.val = val;
}
// *) ------
public static int query(Trie root, int val, int depth, int limit) {
if (root.tag == true) {
if (root.val <= limit) return root.val ^ val;
return -1;
}
int t = (val >> depth) & 0x01;
if (root.child[1 - t] != null && root.child[1 - t].val <= limit) {
int res = query(root.child[1 - t], val, depth - 1, limit);
if (res != -1) return res;
}
if (root.child[t] != null && root.child[t].val <= limit) {
int res = query(root.child[t], val, depth - 1, limit);
if (res != -1) return res;
}
return -1;
}
}
public int[] maximizeXor(int[] nums, int[][] queries) {
// 真的是构建0/1二叉树吗？
Trie root = new Trie();
for (int v: nums) {
Trie.add(root, v);
}
int n = queries.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) {
int[] q = queries[i];
res[i] = Trie.query(root, q[0], gBit, q[1]);
}
return res;
}
}写在最后
评论 (4)
