前言
「唔哇。」 奈芙莲发出听似毫不讶异的惊呼声。
「怎……怎么了啦？」 还保持着警戒姿势的珂朵莉问道。
珂朵莉到目前为止已经被威廉吓够了。如今她无论听到什么都不会心慌，更不会因而露出破绽让威廉趁机击败她。珂朵莉如此告诉自己，并重新将瑟尼欧里斯握好。
「他快死了。」 奈芙莲低语。
「……耶？」 珂朵莉发出了傻里傻气的疑问声。
整体评价
t2易错题， t3贪心，不过要考虑进制，更易错， t4是个奇怪的树。
比赛入口：第 317 场周赛
更多解题报告详见： 珂朵莉MM的解题报告
T1. 可被三整除的偶数的平均值
有2,3互质，其实直接被6整除就行
Java
class Solution {
public int averageValue(int[] nums) {
int cnt = 0;
long sum = 0;
for (int v: nums) {
if (v % 6 == 0) {
cnt++;
sum += v;
}
}
return cnt == 0 ? 0 : (int)(sum / cnt);
}
}T2. 最流行的视频创作者
经典Hash的场景应用题, 不过需要考虑int溢出的情况，还有0的情况。
Java
class Solution {
static class Tx {
String id;
int idCnt;
long total;
}
public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
int n = creators.length;
Map<String, Tx> hash = new TreeMap<>();
long maxV = 0;
for (int i = 0; i < n; i++) {
String c = creators[i];
Tx cur = hash.computeIfAbsent(c, (x) -> new Tx());
if (cur.idCnt < views[i] || (cur.idCnt == views[i] && (cur.id == null || cur.id.compareTo(ids[i]) > 0))) {
cur.idCnt = views[i];
cur.id = ids[i];
}
cur.total += views[i];
maxV = Math.max(cur.total,maxV);
}
List<List<String>> result = new ArrayList<>();
for (Map.Entry<String, Tx> e: hash.entrySet()) {
Tx cur = e.getValue();
if (cur.total == maxV) {
result.add(List.of(e.getKey(), cur.id));
}
}
return result;
}
}T3. 美丽整数的最小增量
贪心，不过要注意进位的情况，超级容易错。
Java
class Solution {
public long makeIntegerBeautiful(long n, int target) {
int total = 0;
List<Integer> arr = new ArrayList<>();
while (n > 0) {
total += (int)(n % 10);
arr.add((int)(n % 10));
n /= 10;
}
if (total <= target) return 0;
long ans = 0l;
long base = 1l;
for (int i = 0; i < arr.size() && total > target; i++) {
int v = arr.get(i);
if (v == 0) {
base *= 10l;
continue;
}
ans += (10 - v) * base;
base *= 10l;
total -= v;
// 处理进位
int c = 1;
int j = i + 1;
while (j < arr.size()) {
int v2 = arr.get(j);
if (v2 + 1 < 10) {
arr.set(j, v2 + 1);
total += 1;
c = 0;
break;
} else {
arr.set(j, 0);
total -= v2;
c = 1;
}
j++;
}
if (c == 1) {
arr.add(1);
total += 1;
}
}
return ans;
}
}T4. 移除子树后的二叉树高度
方法一：按层序分组统计
确实是个脑筋急转弯，如果按照深度分组，这题就是秒杀。
中间想过分治dfs，不知道可不可行，待会再试试。
Java
class Solution {
static class Tx {
int val;
int depth;
public Tx(int val, int depth) {
this.val = val;
this.depth = depth;
}
}
Map<Integer, Integer> map = new TreeMap<>();
TreeMap<Integer, List<Tx>> height = new TreeMap<>();
int dfs(TreeNode root, int depth) {
if (root == null) return depth - 1;
int h = depth;
int h1 = dfs(root.left, depth + 1);
int h2 = dfs(root.right, depth + 1);
h = Math.max(h1, h);
h = Math.max(h2, h);
height.computeIfAbsent(depth, (x) -> new ArrayList<>()).add(new Tx(root.val, h));
map.put(root.val, depth);
return h;
}
void prebuild(TreeNode root) {
dfs(root, 0);
for (Map.Entry<Integer, List<Tx>> e: height.entrySet()) {
Collections.sort(e.getValue(), Comparator.comparing(x -> -x.depth));
}
}
public int[] treeQueries(TreeNode root, int[] queries) {
prebuild(root);
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int level = map.get(queries[i]);
List<Tx> arr = height.get(level);
int ans = level - 1;
// 最多两个
for (int j = 0; j < arr.size() && j < 2; j++) {
Tx cur = arr.get(j);
if (queries[i] != cur.val) {
ans = cur.depth;
break;
}
}
res[i] = ans;
}
return res;
}
}方法二：寻找特殊的长链+增量式重算
首先，可以观察发现，大部分的节点去掉，其对应的最大高度是不会变化的，只有在最长链的节点，才会真正影响树的高度。
基于这个观察或者发现，这题的思路，就是寻找树的最长链，然后特殊处理即可。
一图胜千言
大致的思路如下：
- 预处理，为每个节点计算其深度/高度， 对应dfs
- 启发式合并，主要是寻找到那个特殊的长链， 对应dfs2
- 对特殊长链的特殊处理，增量式重算， 对应dfs3
刚好是三个DFS，累计下来时间复杂度为
Java
class Solution {
// 这个是保存所求的点
Map<Integer, Integer> hash = new HashMap<>();
Map<Integer, Integer> heightMap = new HashMap<>();
Map<Integer, Integer> depthMap = new HashMap<>();
int maxHeight = 0;
// 预处理每个节点的高度和深度
int dfs(TreeNode root, int depth) {
if (root == null) return -1;
int h = Math.max(dfs(root.left, depth + 1), dfs(root.right, depth + 1)) + 1;
depthMap.put(root.val, depth);
heightMap.put(root.val, h);
return h;
}
// 启发式合并 (依赖节点的高度)
List<Integer> dfs2(TreeNode root) {
if (root == null) return new ArrayList<>();
List<Integer> arr1 = dfs2(root.left);
List<Integer> arr2 = dfs2(root.right);
List<Integer> collector = null;
if (root.left != null && root.right != null) {
int h1 = heightMap.get(root.left.val);
int h2 = heightMap.get(root.right.val);
if (h1 == h2) {
arr1.stream().forEach(x -> hash.put(x, maxHeight));
arr2.stream().forEach(x -> hash.put(x, maxHeight));
} else if (h1 > h2) {
arr2.stream().forEach(x -> hash.put(x, maxHeight));
collector = arr1;
} else {
arr1.stream().forEach(x -> hash.put(x, maxHeight));
collector = arr2;
}
} else if (root.left != null) {
collector = arr1;
} else if (root.right != null) {
collector = arr2;
}
if (collector == null) {
collector = new ArrayList<>();
}
if (hash.containsKey(root.val)) {
collector.add(root.val);
}
return collector;
}
Map<Integer, TreeNode> blockMap = new HashMap<>();
int maxHeight2 = 0;
void dfs3(TreeNode root, int block, int depth) {
if (root == null) {
return;
}
if (root.val == block) {
blockMap.put(block, root);
return;
}
maxHeight2 = Math.max(maxHeight2, depth);
dfs3(root.left, block, depth + 1);
dfs3(root.right, block, depth + 1);
}
// 分治法吗？
// 启发式 合并？
public int[] treeQueries(TreeNode root, int[] queries) {
for (int i = 0; i < queries.length; i++) {
hash.put(queries[i], -1);
}
maxHeight = dfs(root, 0);
List<Integer> result = dfs2(root);
// *) 进行逆转
if (result.size() > 0) {
Collections.reverse(result);
for (int i = 0; i < result.size(); i++) {
int v = result.get(i);
if (i == 0) {
dfs3(root, v, 0);
} else {
int pv = result.get(i - 1);
dfs3(blockMap.get(pv), v, depthMap.get(pv));
}
hash.put(v, Math.max(maxHeight2, depthMap.get(v) - 1));
}
}
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
res[i] = hash.get(queries[i]);
}
return res;
}
}方法三：DFS时间戳 + 区间最值查询
真的没想到dfs时间戳技巧，还能这么用。
这个区间转换真的太秒了，而且这个区间最值比较特殊，它是最左侧，最右侧的区间查询。
Java
class Solution {
static final int SIZE = 10_0000;
int[] l = new int[SIZE + 1];
int[] r = new int[SIZE + 1];
int[] depth = new int [SIZE + 1];
int stamp = 0;
void dfs(TreeNode root, int x) {
if (root == null) return;
l[root.val] = ++stamp;
dfs(root.left, x + 1);
dfs(root.right, x + 1);
r[root.val] = stamp;
depth[l[root.val]] = x;
}
public int[] treeQueries(TreeNode root, int[] queries) {
stamp = 0;
dfs(root, 0);
int[] left = new int[stamp + 2];
int[] right = new int[stamp + 2];
for (int i = 1; i <= stamp; i++) {
left[i] = Math.max(depth[i], left[i - 1]);
}
for (int i = stamp; i >= 1; i--) {
right[i] = Math.max(depth[i], right[i + 1]);
}
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int q = queries[i];
res[i] = Math.max(left[l[q] - 1], right[r[q] + 1]);
}
return res;
}
}方法四：分治DFS?
不知道这个算法，是否属于分治DFS的范畴？
Java
class Solution {
static final int SIZE = 10_0000;
int[] height = new int[SIZE + 1];
int[] depth = new int [SIZE + 1];
int[] ans = new int[SIZE + 1];
// 分治DFS
// 预处理深度
int dfs(TreeNode root, int x) {
if (root == null) return x - 1;
int h = Math.max(dfs(root.left, x + 1), dfs(root.right, x + 1));
height[root.val] = x;
depth[root.val] = h;
return h;
}
void dfs2(TreeNode root, int maxHeight) {
ans[root.val] = maxHeight;
if (root.left != null) {
int rv = (root.right != null) ? depth[root.right.val] : height[root.val];
dfs2(root.left, Math.max(maxHeight, rv));
}
if (root.right != null) {
int lv = (root.left != null) ? depth[root.left.val] : height[root.val];
dfs2(root.right, Math.max(maxHeight, lv));
}
}
public int[] treeQueries(TreeNode root, int[] queries) {
dfs(root, 0);
dfs2(root, 0);
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int q = queries[i];
res[i] = ans[q];
}
return res;
}
}写在最后
珂朵莉MM真的是太菜了，关灯吃面去...
评论 (14)
