阿里国际算法类笔试 0828 2.8/3

前面的选择题考的又难又细。
编程题
第一题签到，不过留了一个小坑，如果不用 dict 优化统计字符串 A 和 B 中每个数出现的频率会超时

第二题允许执行任意次操作，每次操作把一个数组内的数全部+1/-1，求两个数组 A, B 之间的最短距离。
转化为求 C=A-B，执行多少次操作后绝对值之和最小。
这题比较啰嗦，需要观察到当 C 中 [负数的数量] 和 [零的数量] 之和大于 [正数数量] 的时候，全部 -1 没有意义。所以当 [正数的数量] > [负数和零的数量] 的时候，假设 k = [正数的数量] - [负数和零的数量]，那么应该把执行 n 次操作，直到 k/2 个正数变成负数或 0. n 的计算就等于第 k/2 大的正数。[负数的数量] > [正数和零的数量] 的时候同理。

第三题给出一棵树，要求任意一个节点做 root 的时候，它所有子树的异或的和。暴力过 10%；加上记忆化搜索（树形 dp）过 45%；再处理一个边界情况：提前计算一下 [整棵树的异或]，当 root 是取的是只有一个 child 的节点的时候，直接返回 root ^ [整棵树的异或]，能过 90%。
有没有大佬指导 100% 的方法

#笔试##阿里#