微软 软开8.19笔试
如无意外感觉终于AK了，只不过第二题自己实现有点复杂，不知道会不会超时呢。。
第一题 修道路
思路：x坐标数组排序+贪心
public int solution(int[] X, int[] Y, int W) {
int length = X.length;
// 定义数组记录修复状态
boolean[] used = new boolean[length];
// 只需要关注横坐标 对其进行排序
Arrays.sort(X);
// 记录结果
int result = 0;
// 遍历一次整个数组
for (int i = 0;i < length;i++) {
// 如果已经修复 则跳过
if (used[i]) {
continue;
}
// 修复当前坑
used[i] = true;
result++;
int cover = X[i]+ W;
// 把在覆盖范围内的坑也修复
for (int j = i + 1;j < length;j++) {
if (X[j] <= cover) {
used[j] = true;
}else {
break;
}
}
}
// 返回结果
return result;
} 第二题 根据给出的字符串（只有0-9）构建最大的回文数字串 "3818286989" -> "9886889"
思路：想不到啥好办法，只能统计一次所有数字出现的次数 出现超过2次的数中按序构建。如果有更好办法的话请指教。
public String solution(String S) {
// 定义一个map存储数字对应出现的次数
Map<Character, Integer> countMap = new HashMap<>();
// 定义一个list存储出现次数大于等于1的数字
List<Character> countList = new ArrayList<>();
// 定义一个Set去存储出现过的数字，方便后续取出只出现一次的最大数
Set<Character> allSet = new HashSet<>();
// 创建结果集
StringBuilder sb = new StringBuilder();
// 遍历一次字符串进行初始化统计
for (char c : S.toCharArray()) {
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
allSet.add(c);
if (countMap.get(c) >= 2) {
countList.add(c);
}
}
// 对countList排序
countList.sort((a, b) -> b - a);
for (char c : countList) {
while (countMap.get(c) >= 2) {
// 使用掉就要减去
countMap.put(c, countMap.get(c) - 2);
if (c == '0' && sb.length() == 0) {
continue;
}
sb.append(c);
}
}
String reverse = new StringBuilder(sb.toString()).reverse().toString();
// 对Set进行排序
List<Character> set = new ArrayList<>(allSet);
set.sort((a, b) -> b - a);
for (Character c : set) {
if (countMap.get(c) > 0) {
sb.append(c);
break;
}
}
sb.append(reverse);
return sb.toString().equals("") ? "0" : sb.toString();
} 思路：由于0是最终的终点，因此可以看成根节点，最终整个道路就是一个多叉树。我采用了递归的方法，每个节点return当前节点的人数，并且在遍历的过程中记录油耗。（难点就在于给出的不是一颗树，而是两个数组，并且边界和细节真的特别特别多，这道题一共写了将近30分钟。。）
public int solution(int[] A, int[] B) {
// 找到与0相接的结点
List<Integer> connectList = find(0, A, B);
for (int i : connectList) {
// 分别递归
dfs(0, i, A, B);
// 每个节点过来都需要汽油
fuel++;
}
return fuel;
}
public int dfs(int parent, int now, int[] A, int[] B) {
// 找到当前节点的相接节点
List<Integer> connectList = find(now, A, B);
// 默认一个人
int people = 1;
for (int i : connectList) {
// 如果与父节点相同则不需要计算
if (i == parent) {
continue;
}
// 获取子节点的人数
int result = dfs(now, i, A, B);
// 每个节点过来都需要汽油
fuel++;
// 人数++
people += result;
}
// 大于5个人的时候需要加汽油
if (people > 5) {
fuel += (people / 5) - 1;
}
return people;
}
// 用于寻找相接的结点
public List<Integer> find(int target, int[] A, int[] B) {
List<Integer> list = new ArrayList<>();
for (int i = 0;i < A.length;i++) {
if (A[i] == target) {
list.add(B[i]);
}
if (B[i] == target) {
list.add(A[i]);
}
}
return list;
} 
