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;
    }
}