微软8.13笔试
1、int数组，用一次过滤器可以将里面某个数过减少一半，求最小过滤次数，使得数组和小于等于原来数组和的一半。
例：（1）、[1,2]，答案是2。第一次过滤2，数组变为[1,1]，和是2>(1+2)/2=1.5. 第二次过滤，数组变为[0.5,1]，和是1.5==(1+2)/2=1.5.
(2)、[1,5],答案是2。第一次过滤5，数组变为[1,2.5]，和是3.5>(1+5)/2=2.5. 第二次过滤，数组变为[1，1.25]，和是2.25<(1+5)/2=2.5.
思路：模拟。优先级队列，每次将最大的数出堆，减半入堆，同时记录最大和和过滤次数，满足条件时终止循环，返回结果。
难点：想到每次过滤最大的这个数。
时空复杂度：nlogn，n。将数组中每个元素放入大根堆中，时间复杂度时nlogn。创建大根堆需要O(n)空间。
解法：
@Test
public void test() {
int solution1 = solution(new int[]{3, 3});
int solution2 = solution(new int[]{1, 3});
System.out.println(solution1);
System.out.println(solution2);
}
public int solution(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res = 0;
// 1、创建大根堆
PriorityQueue<Double> pq = new PriorityQueue<>((a, b) -> (b.compareTo(a)));
double oldSum = 0;
for (int num : nums) {
pq.add((double) num);
oldSum += num;
}
// 2、遍历，更新大根堆，当前和，过滤次数
double curSum = oldSum;
while (curSum > oldSum / 2) {
Double poll = pq.poll();
pq.add(poll / 2);
res++;
curSum -= poll / 2;
}
return res;
} 2、两个int型数组，分别是分子和分母，选择一对分数使得和为1，求有多少对。
例：【1，1，1】，【2，2，2】，答案是3. 【1，2，2】，【3，2，3】，答案是1.
思路：两数之和。
难点：分数之间的减法
时空复杂度：n，n。
解法：
@Test
public void test() {
int solution1 = solution(new int[]{1, 1, 2}, new int[]{3, 2, 3});
System.out.println(solution1);
}
public int solution(int[] nums1, int[] nums2) {
int res = 0;
String[] strs = new String[nums1.length];
for (int i = 0; i < strs.length; i++) {
strs[i] = String.format("%s/%s", nums1[i], nums2[i]);
}
// 两数之和
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
String key = strs[i];
String target = oneMinusKey(key);
if (map.containsKey(target)) {
res += map.get(target);
}
map.put(key, map.getOrDefault(key, 0) + 1);
}
return res;
}
public String oneMinusKey(String x) {
char up = (char) (x.charAt(2) - x.charAt(0) + '0');
char down = x.charAt(2);
return String.format("%s/%s", up, down);
} 3、int数组，int[i]代表第i天的价格，每隔y天付一次钱，一共要做x次。求最小付钱数。 例：[1,4,2,3]，1+2与4+3的最小值。
思路：暴力，求出可以开始遍历的区间，从区间的每个起始位置开始，向后累加x次，同时调整最小值。
难点：不要想复杂，刚开始我想回溯，但肯定超时。后面发现只要向后看就可以了。
时空复杂度：n2，1
解法：
@Test
public void test() {
int solution = solution(new int[]{1, 4, 3, 2}, 1, 2);
System.out.println(solution);
}
public int solution(int[] nums, int x, int y) {
int res = Integer.MAX_VALUE;
int maxStart = nums.length - (x - 1) * y - 1;
for (int i = 0; i < maxStart; i++) {
int curSum = 0, index = i;
for (int j = 0; j < x; j++) {
curSum += nums[index];
index += y;
}
res = Math.min(res, curSum);
}
return res;
} 
