0819微软笔试
problem 1 ：
给定X[],Y[]，组成坑洞坐标，现有填坑机，机器填坑宽度是W，沿y轴平行方向填坑，问最少几台机器可以填补所有的坑？
method： 按照X坐标贪心遍历。
problem 2 :
给定字符串S，求S中某些字符组成的最大回文字符串。
eg: "19878" ---"898"
method: 找所有出现偶数次的数字和一个最大的奇数次的数字，偶数次数字排序，由大到小拼接成字符串，中间加上奇数次的一个数字组成回文字符串。
or dfs求所有子集，遍历得到最大的回文字符串。
problem 3:
给定一些房子和办公楼，两点间有一个路线，无环，每个房子楼下都有一辆车，车最多坐5个人，两点间消耗1L油，问，所有房子里的人到达办公楼所需的最小油。
method： 图的bfs遍历，两点间油消耗随此房间当时的人数而变即可。
import java.util.Arrays;
import java.util.LinkedList;
public class Main20 {
public static void main(String[] args) {
int[] A = new int[]{1,1,1,9,9,9,9,7,8};
int[] B = new int[]{2,0,3,1,6,5,4,0,0};
int res = solution(A, B);
System.out.println(res);
}
public static int solution(int[] A, int[] B) {
// write your code in Java 8 (Java SE 8)
//建造入度与邻接矩阵
int[] inDegree = new int[A.length + 1];
int[][] matrix = new int[A.length + 1][A.length + 1];
for(int i = 0; i < A.length; i++){
matrix[A[i]][B[i]]++;
matrix[B[i]][A[i]]++;
inDegree[A[i]]++;
inDegree[B[i]]++;
}
int[] val = new int[A.length + 1];
//每个节点的初始人数
Arrays.fill(val, 1);
LinkedList<Integer> queue = new LinkedList();
for(int i = 1; i < inDegree.length; i++){
if(inDegree[i] == 1){
//即入度为1且不是办公区0的房子入队
queue.add(i);
}
}
int res = 0;
while(!queue.isEmpty()){
int len = queue.size();
for(int i = 0; i < len ; i++){
int tmp = queue.remove();
//将此房子的人移到另一个房子内即可
//计算移动当前房间人所需的油
if(val[tmp] % 5 == 0){
res += val[tmp] / 5;
}else{
res += val[tmp] / 5 + 1;
}
//找到其下一个房子是哪个
for(int j = 0; j < inDegree.length; j++){
if(matrix[tmp][j] == 1){
matrix[tmp][j]--;
matrix[j][tmp]--;
inDegree[j]--;
inDegree[tmp]--;
//非办公区的房子且入度为1，入队
if(j != 0 && inDegree[j] == 1){
queue.add(j);
}
//人数要加上之前的人
val[j] += val[tmp];
}
}
}
}
return res;
}
}
投递萤石等公司10个岗位