微软笔试代码交流8.13

贴一下题目吧，从别的帖子捞过来的😂😂😂

微软笔试是两点结束吗？那就等会再发吧

上周的笔试写完第一题后就点了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;
    }