9.14 京东笔试 AK

第一题：前缀和

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] preSum = new int[n + 1];
        String[] as = reader.readLine().split(" ");
        for (int i = 0; i < n; ++ i) preSum[i + 1] = preSum[i] + Integer.parseInt(as[i]);

        long ans = Long.MAX_VALUE;
        for (int i = 1; i <= n - 1; ++ i) {
            int left = preSum[i];
            int right = preSum[n] - preSum[i];
            ans = Math.min(ans, (long) left * right);
        }

        System.out.println(ans);
    }
}

第二题：第一行的字符串重新定义了字典序，修改一下比较器就行

private static void extracted() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        int[] rank = new int['z' + 1];
        for (int i = 0; i < str.length(); ++ i) {
            rank[str.charAt(i)] = i;
        }
        int n = Integer.parseInt(reader.readLine());
        String[] input = new String[n];
        for (int i = 0; i < n; ++ i) input[i] = reader.readLine();

        Arrays.sort(input, (str1, str2) -> {
            int i = 0, j = 0, n1 = str1.length(), n2 = str2.length();
            while (i < n1 && j < n2) {
                int diff = rank[str1.charAt(i)] - rank[str2.charAt(j)];
                if (diff != 0) {
                    return diff;
                }
                i++;
                j++;
            }
            if (i == n1) {
                return j == n2 ? 0 : -1;
            } else {
                return 1;
            }
        });

        for (String s : input) {
            System.out.println(s);
        }
    }

第三题：最小生成树中最长边

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[][] city = new int[n][2];
        for (int i = 0; i < n; ++ i) {
            String[] s = reader.readLine().split(" ");
            city[i][0] = Integer.parseInt(s[0]);
            city[i][1] = Integer.parseInt(s[1]);
        }
        int len = n * (n - 1) / 2;
        Node[] edges = new Node[len];

        int k = 0;
        for (int i = 0; i < n; ++ i) {
            for (int j = i + 1; j < n; ++ j) {
                edges[k ++] = new Node(i, j, getDistance(city[i][0], city[i][1], city[j][0], city[j][1]));
            }
        }

        Arrays.sort(edges, (e1, e2) -> {
            double diff = e1.distance - e2.distance;
            if (diff < 0) return -1;
            else if (diff == 0) return 0;
            else return 1;
        });

        UnionFind uf = new UnionFind(n);
        double longEdge = 0;
        for (Node edge : edges) {
            int c1 = edge.c1, c2 = edge.c2;
            double dis = edge.distance;
            if (uf.union(c1, c2)) continue;
            longEdge = Math.max(longEdge, dis);
        }

        System.out.println((int)(longEdge / 2 + 0.5));
    }

    static class Node {
        int c1, c2;
        double distance;
        public Node(int c1, int c2, double distance) {
            this.c1 = c1;
            this.c2 = c2;
            this.distance = distance;
        }
    }

    static class UnionFind {
        public int[] parent;
        public int setCount;
        public int[] count;
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; ++ i) parent[i] = i;
            count = new int[n];
            Arrays.fill(count, 1);
            setCount = n;
        }

        public int find(int x) {
            return parent[x] == x ? parent[x] : (parent[x] = find(parent[x]));
        }

        public boolean union(int x, int y) {
            int pX = find(x);
            int pY = find(y);
            if (pX == pY) return true;
            if (count[pX] > count[pY]) {
                int t = pX;
                pX = pY;
                pY = t;
            }
            count[pY] += count[pX];
            parent[pX] = pY;
            return false;
        }
    }

    static double getDistance(int x1, int y1, int x2, int y2) {
        int deltaX = x1 - x2, deltaY = y1 - y2;
        return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
    }

总体来说，今天的题比较简单