京东笔试真题

京东笔试0315

数组价值

分析

比较最大元素-第二小元素和第二大元素-最小元素，取较小值。

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        // 循环处理输入
        for (int t = 0; t < T; t++) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            // 排序
            Arrays.sort(nums);
            // 比较
            int x = nums[n-1] - nums[1];
            int y = nums[n-2] - nums[0];
            System.out.println(Math.min(x, y));
        }
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

小兴的涂色面积

找规律

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();  // 输入初始半径
        int n = sc.nextInt();  // 输入层数
        
        // 第一层圆的面积，计算初始的 total
        double total = Math.PI * r * r * 3 / 4;
        
        // 从第二层到第n层，逐层计算圆的面积
        for (int i = 2; i <= n; ++i) {
            r = r / 2;  // 半径是上一层的半径的一半
            double m = Math.PI * r * r;  // 计算当前层圆的面积
            
            // 根据层数的奇偶性，调整总面积
            if (i % 2 == 0) {
                total -= m * 3 / 4;  // 偶数层，面积减去
            } else {
                total += m * 3 / 4;  // 奇数层，面积加上
            }
        }
        
        // 输出最终结果，保留7位小数
        System.out.printf("%.2f\n", total);
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

快递

最短路径

1. Dijkstra 算法的核心：

   • 初始化：起始节点的最短路径设为 0，其他节点设为 INF。
   • 处理优先队列：每次从队列中取出当前最短路径的节点，并更新它的邻接节点的最短路径。如果通过当前节点的路径更短，就
   • 新邻接节点的最短路径并将它加入队列。
   • 终止条件：当队列为空时，表示所有可达节点的最短路径已计算完成。

2. 图的构建：

   • 输入读取：读取节点和边的信息，构建图的邻接列表。
   • 特殊节点的处理：将每个特殊节点与新节点 n 连接，边的权重为 0，确保从特殊节点到新节点的路径是“可达的”。

3. 查询处理：

   • 对于每个查询，直接输出从新节点 n 到目标节点的最短路径。

import java.util.*;

public class Main {
    static final long INF = Long.MAX_VALUE;
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入基本信息
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();
        // 输入k个快递点
        List<Integer> stations = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            stations.add(sc.nextInt());
        }
        
        // n 增加 1，考虑到节点编号是从 1 开始，所以需要把图大小调整为 n+1
        n++;
        // 创建邻接列表 graph，存储图的结构
        List<List<Pair>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>()); // 初始化每个节点的邻接列表
        }
        
        // 读取图的边信息，构建无向图
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(); // 边的一个端点
            int b = sc.nextInt(); // 边的另一个端点
            int c = sc.nextInt(); // 边的权重（距离）
            // 在 a 和 b 之间添加一条边
            graph.get(a).add(new Pair(c, b)); 
            graph.get(b).add(new Pair(c, a)); // 因为是无向图，a 和 b 之间的边是双向的            
        }
        
        // 将每个特殊节点与新节点 n 连接，边的权重为 0
        for (int sn : stations) {
            graph.get(sn).add(new Pair(0, n)); // 从特殊节点到新节点 n，权重为 0
            graph.get(n).add(new Pair(0, sn)); // 从新节点 n 到特殊节点，权重为 0
        }
        
        // 使用 Dijkstra 算法计算从新节点 n 到所有其他节点的最短路径
        long[] distances = dijkstra(graph, n, n);

        // 处理查询，输出从新节点 n 到目标节点的最短路径
        for (int i = 0; i < q; i++) {
            int target = sc.nextInt(); // 读取查询的目标节点
            System.out.println(distances[target]); // 输出从新节点 n 到目标节点的最短路径
        }

        // 关闭 Scanner
        sc.close();
    }
    
    // Dijkstra 算法，计算从起始节点到所有其他节点的最短路径
    public static long[] dijkstra(List<List<Pair>> graph, int n, int start) {
        // 创建一个数组 dist，用来存储从 start 到各个节点的最短路径
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        
        // 创建一个布尔数组 visited，用来标记节点是否已经被访问过
        boolean[] visited = new boolean[n + 1];
        
        // 优先队列，按照最短路径优先处理节点
        // Pair 是 (dist, node) 的形式，dist 表示从起始节点到当前节点的最短路径，node 是当前节点
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingLong(pair -> pair.dist));
        // 把起始节点加入队列
        pq.offer(new Pair(0, start));
        
        // 当队列不为空时，持续进行以下步骤
        while (!pq.isEmpty()){
            // 取出当前队列中最短路径的节点
            Pair cur = pq.poll();
            int u = cur.node;
            long curDist = cur.dist;
            
            // 如果已访问过，跳过
            if (visited[u]) {
                continue;
            }
            visited[u] = true;
            
            // 遍历当前节点的所有邻接节点，更新它们的最短路径
            for (Pair neighbor : graph.get(u)) {
                int v = neighbor.node; // 邻接节点编号
                long weight = neighbor.dist; // 当前边的权重（即从 u 到 v 的距离）                
                // 如果通过当前节点 u 到达 v 的路径更短，更新 dist[v] 并将 v 加入队列
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new Pair(dist[v], v));
                }
            }
        }
        // 返回从 start 到所有节点的最短路径
        return dist;
    }
    
    // 定义一个 Pair 类，表示 (dist, node)，即一个节点和它的最短路径
    static class Pair {
        long dist;
        int node;
        
        // 构造方法
        Pair(long dist, int node) {
            this.dist = dist;
            this.node = node;
        }
    }
}

• 时间复杂度：O(E log V)
• 空间复杂度：O(n + m + k)

总结

京东的题目不是很难，但要完全写对也不容易，之后要找迪杰斯特拉的题目再练练。