师姐笔试复盘（字节 9.12 测开）
1. 和师姐思路一样，，用哨兵变量存开始时间和结束时间的相关信息，set存所有的时间点，遍历即可。但是只过了30，看讨论区应该是输入超时了。
import java.util.*;
public class zj_2021_01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = Integer.MIN_VALUE;
Map<Integer, Integer> start = new HashMap<>();
Map<Integer, Integer> end = new HashMap<>();
TreeSet<Integer> times = new TreeSet<>();
for (int i = 0; i < n; i++) {
int s = sc.nextInt();
times.add(s);
start.put(s, start.getOrDefault(s, 0) + 1);
int e = sc.nextInt() + s;
times.add(e);
end.put(e, end.getOrDefault(e, 0) + 1);
}
int cnt = 0;
for (int time : times) {
cnt += start.getOrDefault(time, 0);
cnt -= end.getOrDefault(time, 0);
max = Math.max(cnt, max);
}
System.out.println(max);
}
} 2. 师姐没做出来，我的思路是递归判断+输出，不知道对不对，用了一个存深度的数组，依次存中序遍历相应位置的深度，假如是回文的那就是对称的树，最后直接输出。 import java.util.*;
public class zj_2021_02 {
static HashMap<Integer, Integer> inorder_idx;
static int[] preorder;
static int[] inorder;
static int[] inorder_height;
static int max_idx = 0;
static int n;
static boolean flag = true;
public static void isMirror (int preorder_left, int preorder_right, int inorder_left, int inorder_right, int height) {
if (preorder_left > preorder_right || inorder_left > inorder_right) {
return;
}
int inorder_root = inorder_idx.get(preorder[preorder_left]);
inorder_height[inorder_root] = height;
int other_height = inorder_height[n - 1 - inorder_root];
if (!flag || (other_height != 0 && other_height != height)) {
flag = false;
return;
}
int left_size = inorder_root - inorder_left;
isMirror(preorder_left + 1, preorder_left + left_size, inorder_left, inorder_root - 1, height + 1);
isMirror(preorder_left + left_size + 1, preorder_right, inorder_root + 1, inorder_right, height + 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
preorder = new int[n];
inorder = new int[n];
inorder_height = new int[n];
for (int i = 0; i < n; i++) {
preorder[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
inorder[i] = sc.nextInt();
max_idx = inorder[i] > inorder[max_idx] ? i : max_idx;
}
inorder_idx = new HashMap<Integer, Integer>();
for (int i = 0; i < inorder.length; i++) {
inorder_idx.put(inorder[i], i);
}
isMirror(0, n - 1, 0, n - 1, 0);
System.out.println(flag ? inorder[n - 1- max_idx] : inorder[max_idx]);
}
}