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;
}
} 第三题，分组然后滑动窗口