T1: 可被3整数的偶数的平均值
思路：数组遍历
被3整数的偶数 \(\Leftrightarrow\) 被6整数的数
public int averageValue(int[] nums) {
int sum = 0;
int count = 0;
for (int num : nums) {
if (num % 6 == 0) {
sum += num;
count += 1;
}
}
if (count == 0) {
return 0;
}
return sum / count;
}
T2: 最流行的视频创作者
思路：数组遍历 + 哈希
key: 对应创作者
value: 对应一个列表，list.get[0]表示创作者视频流量总和，list.get[1]表示创作者单个视频流量最大值，list.get[3] 表示创作者单个视频流量最大值对应的id
public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
Map<String, List<String>> map = new HashMap<>();
long maxValue = 0;
for (int i = 0; i < creators.length; ++i) {
if (!map.containsKey(creators[i])) {
maxValue = Math.max(maxValue, views[i]);
List<String> list = new ArrayList<>();
list.add(String.valueOf(views[i]));
list.add(String.valueOf(views[i]));
list.add(ids[i]);
map.put(creators[i], list);
}
else {
List<String> list = map.get(creators[i]);
long sum = Long.valueOf(list.get(0));
int max = Integer.valueOf(list.get(1));
sum += views[i];
maxValue = Math.max(maxValue, sum);
if (max < views[i]) {
list.set(2, ids[i]);
max = views[i];
}
else if (max == views[i]) {
if (list.get(2).compareTo(ids[i]) > 0) {
list.set(2, ids[i]);
}
}
list.set(0, String.valueOf(sum)); // 总体流量总和
list.set(1, String.valueOf(max)); // 单个作者最大值
map.put(creators[i], list);
}
}
List<List<String>> res = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
String key = entry.getKey();
List<String> value = entry.getValue();
if (Long.valueOf(value.get(0)) == maxValue) {
List<String> temp = new ArrayList<>();
temp.add(key);
temp.add(value.get(2));
res.add(temp);
}
}
return res;
}
T3: 美丽整数的最小增量
思路：贪心
如果低位的值 value 不等于0，则使该为加上 10 - value 产生进位，从而减小数位和
循环向高位贪心直至数位和满足小于等于 target 的要求
public long makeIntegerBeautiful(long n, int target) {
List<Integer> list = new ArrayList<>();
int bitSum = 0;
while (n > 0) {
int temp = (int) (n % 10);
n /= 10;
bitSum += temp;
list.add(temp);
}
if (bitSum <= target) {
return 0;
}
int index = 0;
long ans = 0;
while (bitSum > target) {
int bit = list.get(index);
if (bit == 0) {
index += 1;
continue;
}
ans = ans + (long) Math.pow(10, index) * (10 - bit);
index += 1;
int temp = index;
// 注意：如果左边第一位为9，会循环产生进位
while (temp < list.size() && list.get(temp) == 9) {
list.set(temp, 0);
bitSum -= 9;
temp += 1;
}
if (temp == list.size()) {
list.add(1);
}
else {
list.set(temp, list.get(temp) + 1);
}
bitSum = bitSum - bit + 1;
}
return ans;
}
T4: 移除子树后的二叉树高度
思路：深度优先搜索
第一次深度优先搜索：计算每个节点的高度值
第二次深度优先搜索：计算去除当前节点为根是子树后，剩余子树的高度值
private Map<TreeNode, Integer> map = new HashMap<>();
private int[] res;
public int[] treeQueries(TreeNode root, int[] queries) {
dfs(root);
map.put(null, 0);
res = new int[map.size() + 1];
dfs2(root, -1, 0);
for (int i = 0; i < queries.length; ++i) {
queries[i] = res[queries[i]];
}
return queries;
}
/**
* 第一次DFS: 获取每个节点的高度
* @param node
* @return
*/
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int height = 1 + Math.max(dfs(node.left), dfs(node.right));
map.put(node, height);
return height;
}
/**
* 第二次DFS: 删除以当前节点为根的子树后, 剩余子树的最大高度
* @param node: 当前节点
* @param height: 当前节点高度
* @param residue: 去除以当前节点为根的子树的高度
*/
private void dfs2(TreeNode node, int height, int residue) {
if (node == null) {
return;
}
height += 1;
res[node.val] = residue;
dfs2(node.left, height, Math.max(residue, height + map.get(node.right)));
dfs2(node.right, height, Math.max(residue, height + map.get(node.left)));
}
总结
前3题完成的都挺顺利
第4题思路能想到是 DFS，但是自己每次不同的 query 都去深搜导致超时，没能想到第一遍深搜统计高度值，第二遍深搜计算答案
