0819 微软23校招第三次笔试
题目：
1. X-Y坐标轴上有多个凹槽需要填平，给出一个X数组，X[i]记录第i个凹槽的x坐标；给出一个Y数组，Y[i]记录第i个凹槽的y坐标。填平使用的仪器每次从X轴的某个点向y轴正方向出发，宽度为W，即如果从(x, 0)出发，那么可以覆盖填平范围从X = x到X = x + W（两边都是闭区间）两条线内所有凹槽。问最少用多少次可以填平所有凹槽。
2. 给出一个字符串，只包含0-9的数字，要求使用这些数字构成最大的回文数字（字符串），如给出"39878"，则应返回"898"；如给出"00900"，则应返回"9"；如给出"0000"，则应返回"0"；如给出"54321"，则应返回"5"。
3. 图：一个镇上有N条路，连接了N+1个点（所有点都可以到达，没有循环），标号从0到N，除了点"0"，其他点上都有一个人。每个人每天都需要去点"0"上班，并且可以开车，每辆车最多可以坐5人，每辆车从一个点到相邻的点需要消耗1L油，每个人都可以与其他人拼车。问让所有人都上班的方案中，耗油量最少为多少？
思路：
1. 贪心：不用管Y坐标，把所有凹槽的X坐标加入优先队列，从X最小的点开始遍历，遇到一个凹槽就答案+1，并且之后遇到的凹槽里如果x'坐标小于当前填平的起始坐标x + W就跳过，否则更新答案和起始坐标x。
2. 贪心：从最大数字开始遍历，不论是否是奇数个还是偶数个，统统取偶数个进行构造（0除外），最后选一个最大的奇数个的数字放在正中央
3. BFS：先构造图，并用一个Map记录每个点对应的人数（初始化都为1），然后从图的最外侧（leaves）开始进行BFS遍历，每次遍历到一个点就更新图，同时更新每个点的人数和耗油量（遇到点"0"不更新人数，只更新耗油量），当只剩一个点（点"0"）的时候停止循环。
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
// write your code in Java 8 (Java SE 8)
// 1. 构建图
int nodes = A.length + 1;
Map<Integer, Integer> people = new HashMap<>();
List<Set<Integer>> map = new ArrayList<>();
for (int i = 0; i < nodes; ++i) {
map.add(new HashSet<Integer>());
people.put(i, 1);
}
for (int i = 0; i < A.length; ++i) {
map.get(A[i]).add(B[i]);
map.get(B[i]).add(A[i]);
}
// 2. 找到所有leaves
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < nodes; ++i) {
if (map.get(i).size() == 1) {
leaves.add(i);
}
}
// 3. 从最外层向里bfs
int consume = 0;
int remaining = nodes;
while (remaining > 1) {
remaining -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int leave : leaves) {
// 当前的点
int currPoint = leave;
int currPeople = people.get(currPoint);
// 要去的点
int nextPoint = map.get(currPoint).iterator().next();
if (nextPoint == 0) {
people.remove(currPoint);
consume += (currPeople + 5 - 1) / 5;
map.get(nextPoint).remove(currPoint);
} else {
int nextPeople = people.get(nextPoint);
// 移动点之间的人，并且计算消耗
people.put(nextPoint, currPeople + nextPeople);
people.remove(currPoint);
consume += (currPeople + 5 - 1) / 5;
// 删除连接关系
map.get(nextPoint).remove(currPoint);
// 如果他们的连接只有1个，加入leaves
if (map.get(nextPoint).size() == 1) {
newLeaves.add(nextPoint);
}
}
}
leaves = newLeaves;
}
return consume;
}
} 
查看19道真题和解析