贴一下题目吧,从别的帖子捞过来的😂😂😂
微软笔试是两点结束吗?那就等会再发吧
上周的笔试写完第一题后就点了submit,然后就结束了,哭死😂😂😂。希望这次能过吧,贴一下代码,供大家参考
第二题的时间复杂度不知道顶不顶得住,其他两题感觉应该还ok
// 第一题:将A中的某个数字减少一半,最少需要多少次后,数组的和小于等于原来数组和的一半 // 思路:贪心,大根堆 public int solution(int[] A) { // write your code in Java 8 (Java SE 8) PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> { if (a.equals(b)) return 0; else return a > b ? -1 : 1; }); int sum = 0; for (int n : A) { sum += n; heap.offer((double) n); } int res = 0; double reduce = 0; while (reduce * 2 < sum) { double cur = heap.poll(); cur /= 2; reduce += cur; heap.offer(cur); res++; } return res; }
// 第二题,x[i]/y[i] + x[j]/y[i] = 1的pair数,对1e9+7取模 // 思路:双指针,两数之和 public int solution(int[] X, int[] Y) { // write your code in Java 8 (Java SE 8) int mod = (int) (1e9 + 7); int n = X.length; double[] fractions = new double[n]; for (int i = 0; i < n; i++) { fractions[i] = ((double) X[i]) / Y[i]; } Arrays.sort(fractions); long res = 0; for (int i = 0, j = n - 1; i < j; ) { double sum = fractions[i] + fractions[j]; if (sum == 1) { int left = 1, right = 1; while (i + 1 < n && fractions[i] == fractions[i + 1]) { i++; left++; } while (j - 1 >= 0 && fractions[j] == fractions[j - 1]) { j--; right++; } if (i < j) { res = (res + left * right % mod) % mod; } else { res = (res + (left - 1) * left / 2 % mod) % mod; } i++; j--; } else if (sum > 1) { j--; } else { i++; } } return (int) res; }
感谢评论区大佬的思路,更新下第二题map做法
// 第二题,x[i]/y[i] + x[j]/y[i] = 1的pair数,对1e9+7取模 // 思路:map public int solution(int[] X, int[] Y) { // write your code in Java 8 (Java SE 8) int mod = (int) (1e9 + 7); int n = X.length; long res = 0; Map<Integer, Map<Integer, Integer>> map = new HashMap<>(); for (int i = 0; i < n; i++) { int gcg = gcd(X[i], Y[i]); int up = X[i] / gcg; int down = Y[i] / gcg; Map<Integer, Integer> curMap = map.computeIfAbsent(down, k -> new HashMap<>()); res = (res + curMap.getOrDefault(down - up, 0)) % mod; curMap.put(up, curMap.getOrDefault(up, 0) + 1); } return (int) res; } public int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
// 第三题,数组A中每间隔Y-1个的连续X个数的最小和 // 思路:滑动窗口 public int solution(int[] A, int X, int Y) { // write your code in Java 8 (Java SE 8) int n = A.length; int res = Integer.MAX_VALUE; for (int i = 0; i < Y; i++) { int left = i, right = i; int sum = 0; int count = 0; while (right < n) { sum += A[right]; right += Y; count++; while (count == X) { res = Math.min(res, sum); sum -= A[left]; left += Y; count--; } } } return res; }
全部评论
(25) 回帖