8.13微软笔试

8.13微软笔试，有时间差大家还是别那么早公开发出来比较好。现在2点10分过了都交卷了，可以讨论一下了。

第一题就贪心，用堆排序一下，就是不知道用double会不会损失精度

class Solution1{
    public int solution(int[] A) {
        // write your code in Java 8 (Java SE 8)
        PriorityQueue<Double> priorityQueue = new PriorityQueue<>(new Comparator<Double>() { @Override public int compare(Double o1, Double o2) {
                return (int) (o2-o1);
            }
        });
        double sum = 0.0;
        for(int num:A){
            priorityQueue.add((double)num);
            sum+=num;
        }
        int n = 0;
        sum = sum/2.0;
        double cur = 0.0;
        while (cur<sum){
            double d = priorityQueue.poll();
            cur+=d/2;
            priorityQueue.add(d/2);
            n++;
        }
        return n;
    }
}

第二题两数和，直接存double可能不太行，不知道会不会精度损失。我是先求最大公约数然后约分，把分子分母写了一个point类重写hash和equals方法，然后map中key放point，value放出现次数

class Solution2{
    class Point{
        int a;
        int b;

        public Point(int a, int b) {
            this.a = a;
            this.b = b;
        } @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return a == point.a &&
                    b == point.b;
        } @Override public int hashCode() {
            return Objects.hash(a, b);
        }
    }
    public int solution(int[] X, int[] Y) {
        // write your code in Java 8 (Java SE 8)
        Map<Point,Integer> map = new HashMap<>();
        for (int i = 0; i < X.length; i++) {
            int m = gcd(X[i],Y[i]);
            int x = X[i]/m;
            int y = Y[i]/m;
            X[i] = x;
            Y[i] = y;
            Point p = new Point(x,y);
            if(map.containsKey(p)){
                map.put(p,map.get(p)+1);
            }
            else{
                map.put(p,1);
            }
        }
        int res = 0;
        for (int i = 0; i < X.length; i++) {
            int x = X[i];
            int y = Y[i];
            Point p = new Point(y-x,y);
            if(map.containsKey(p)){
                res+=map.get(p);

            }
            if(2*x==y)res--;
            if(res>=2000000014)res-=2000000014;
        }
        return res/2;
    }
    public int gcd(int a,int b){
        int tmp = a%b;
        while (tmp!=0){
            a = b;
            b = tmp;
            tmp = a%b;
        }
        return b;
    }
}

第三题，分组然后滑动窗口

#微软##笔试##校招#