2024届校招-Java开发笔试题-S4卷

有三种题型：单项选择题（10道）、不定项选择题（10道）、编程题（3道）

下面是一些回忆的题目：

1.哪种设计模式将对象的创建与使用分离，通过工厂类创建对象

答：工厂模式
工厂模式是一种创建型设计模式，它旨在将对象的创建与使用分离。通过引入一个工厂类，客户端代码可以委托工厂类来创建所需的对象，而不必直接实例化对象。这有助于降低耦合度并提高代码的可维护性。

2.运行中的线程，执行Thread.sleep（5000）方法后，，当时间过去5s后，线程状态为

答：可运行（Runnable）状态，等待系统调度来继续执行。

3.new java.math.Big Decimal（0.1）是否会丢失精度
答：不会，BigDecimal类是用来表示精确的任意精度的十进制数，不会引发浮点数的精度问题。然而，如果使用浮点数字面值（例如0.1）来初始化BigDecimal，那么在转换过程可能会引发精度问题，应使用字符串初始化BigDecimal，直接将字符串文本转换为BigDecimal。

4.关于@Import注解的选择题

答：@Import注解是Java Spring 框架中的一个注解，用于在配置类中引入其他配置类，从而将它们的配置合并到当前配置中。它允许开发者在一个配置类中引入其他配置，以便组织和管理Spring应用程序的配置。
@Import注解动态注入方式可通过使用ImportSelector接口的类来实现。但并不是唯一的方式，还可以通过条件化的@Import注解、编程方式的条件化注入、条件化的BeanDefinition注册。

5.创建型设计模式有哪些？

答：创建型设计模式是一种软件设计模式，它们关注如何创建对象，以便在应用程序中更灵活、更高效地管理对象的创建和初始化。以下是一些常见的创建型设计模式：单例模式（Singleton Pattern）、工厂模式（Factory Pattern）、抽象工厂模式（Abstract Factory Pattern）、建造者模式（Builder Pattern）、原型模式（Prototype Pattern）

6.快速排序最坏时间复杂度？
O(n^2)，平均时间复杂度为O(n*log(n))

7.匹配“一”“二”“三”……“十”的中文正则表达式是
[一二三四五六七八九十]

8.哪些场景适合使用NIO模型？

Java NIO(New I/O)模型适合处理需要高并发、高吞吐量和低延迟的网络通信和文件I/O场景。以下是一些适合使用NIO模型的常见场景：网络编程、文件I/O、多路复用、实时数据处理、高性能代理和网关

9.哪些集合类是线程安全的？

答：集合类的线程安全意味着多个线程可以同时访问和修改这些集合而不会导致数据不一致或抛出并发异常。以下是一些线程安全的集合类：Vector、HashTable、ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentLinkedQueue、BlockingQueue。

10.哪些属于进程同步机制？

答：线程同步机制是用于协调和管理多个进程之间的执行顺序以及访问共享资源的一组技术。以下是一些常见的进程同步机制：互斥锁（Mutex）、信号量（Semaphore）、条件变量（Condition Variable）、屏障（Barrier）、读写锁（Read-Write Lock）、管程（Monitor）、自旋锁（Spin Lock）、消息传递

11. 当浏览器缓存中有缓存版本时，哪个HTTP响应头字段可以用于验证缓存是否仍然有效
    答：ETag（实体标签）、Last-Modified（最后修改时间）

12. 哪些可以增强Cookie的安全性

答：使用HTTPOnly标志；使用Secure标志、设置Cookie的SameSite属性;限制Cookie的有效期；对Cookie的内容进行加密;在服务器端验证Cookie；实施双重身份验证（2FA）；定期更改Cookie值；监控和审计；

编程题：

1. 有n个城市通过m个航班连接。每个航班都从城市u开始，以价格w抵达v。现在给定所有的城市和航班，以及出发城市src，你的任务是找到从src城市出发到其他所有城市最便宜的机票价格列表。
   如果无法从src到达某个城市，则他们的价格-1表示。
   输入n=3，edges=[[0,1,100],[1,2,100],[0,2,500],src=0
   输出：[0,100,200]

/**
 * 有n个城市通过m个航班连接。每个航班都从城市u开始，以价格w抵达v。现在给定所有的城市和航班，以及出发城市src，
 * 你的任务是找到从src城市出发到其他所有城市最便宜的机票价格列表。
 * 如果无法从src到达某个城市，则他们的价格-1表示。
 *
 * 输入n=3，edges=[[0,1,100],[1,2,100],[0,2,500],src=0
 * 输出：[0,100,200]
 *
 *
 */


import java.util.*;
public class CheapestPrices {
    public int[] findCheapestPrice(int n, int[][] flights, int src) {
        //n代表城市个数
        //flights 是一个包含多个一维数组的二维数组。每个一维数组都表示一条航班的信息,
        //flights[i][0] 是起始城市的编号，flights[i][1] 是目标城市的编号，flights[i][2] 是航班的价格。
        //src 代表出发城市，题目的意思就是要找出从src出发到其他所有城市出发最便宜的价格。
        // 创建一个邻接表来表示城市之间的航班价格
        List<int[]>[] graph = new List[n];
        //graph[i] 存储与城市 i 相关的航班信息。
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();//表示每个索引 i 处的元素都是一个空的整数数组列表。
        }
        for (int[] flight : flights) { //这段循环用于将航班信息从二维数组 flights 添加到图数据结构 graph 中
            int u = flight[0];
            int v = flight[1];
            int w = flight[2];
            graph[u].add(new int[]{v, w});//将一个新的整数数组 {v, w} 添加到列表中
        }

        // 初始化距离数组，初始距离为无穷大
        int[] distances = new int[n];//该数组用来存储从出发城市 src 到其他城市的距离信息
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[src] = 0;//将出发城市 src 到自身的距离设置为0

        // 使用最小堆来进行Dijkstra算法
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);//minHeap用于存储待处理的节点
        minHeap.offer(new int[]{src, 0});//将出发城市 src 到自身的距离为0的节点添加到优先队列

        while (!minHeap.isEmpty()) {
            int[] current = minHeap.poll();//从优先队列 minHeap 中取出队首元素，即距离最短的节点
            int currentCity = current[0];//current[0] 表示当前节点的城市编号
            int currentCost = current[1];//current[1] 表示从起始城市到当前城市的距离。
            //用于检查当前节点的距离是否已经被更新过
            //如果 currentCost 大于 distances[currentCity]，
            //则表示已经有更短的路径到达当前城市，因此可以忽略当前节点，继续处理下一个节点
            if (currentCost > distances[currentCity]) {
                continue;
            }

            for (int[] neighbor : graph[currentCity]) {
                int neighborCity = neighbor[0];//neighbor[0] 表示邻居城市的编号
                int neighborCost = neighbor[1];//neighbor[1] 表示从当前城市到邻居城市的距离（权重）。
                int newCost = currentCost + neighborCost;

                if (newCost < distances[neighborCity]) {
                    distances[neighborCity] = newCost;
                    minHeap.offer(new int[]{neighborCity, newCost});
                    //将该数组添加到优先队列 minHeap 中，以便稍后继续处理该邻居节点。
                    // 这确保了算法在接下来的迭代中考虑到了邻居节点。
                }
            }
            //通过这段循环，算法不断地探索从当前节点到其邻居节点的可能路径，并更新到达邻居节点的最短距离。
            // 如果找到更短的路径，就会将邻居节点添加到优先队列中，以便后续继续处理。这是Dijkstra算法的关键步骤，
            // 确保找到从出发城市到其他城市的最短路径。
        }

        // 将无法到达的城市的距离设为-1
        for (int i = 0; i < n; i++) {
            if (distances[i] == Integer.MAX_VALUE) {
                distances[i] = -1;
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        CheapestPrices solution = new CheapestPrices();
        int n = 3;
        int[][] edges = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        int src = 0;
        int[] output = solution.findCheapestPrice(n, edges, src);

        // 输出最便宜的机票价格列表
        for (int price : output) {
            System.out.print(price + " ");
        }
        // 输出: 0 100 200
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

2.给定一个任意矩阵（用二维数组表示），要求从左上角移动至右下角，每次只能向下或向右移动一格，矩阵中的数字为本次移动的收益，请算出移动值右下角时，所经过路径和的最大收益。

import java.util.*;

public class maxPathSum {
    public  static int maxPathSum(int[][] matrix){
        if(matrix==null||matrix.length==0||matrix[0].length == 0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int dp[][] = new int[m][n];

        dp[0][0] = matrix[0][0];
        for(int j=1;j<n;j++){
            dp[0][j] = dp[0][j-1]+matrix[0][j];
        }
        for(int i=1;i<n;i++){
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[m-1][n-1];
    }
    public static void main(String[] args) {
        int [][] matrix={
            {1,2,3},
            {4,7,6},
            {5,8,9},
        };
        int maxSum = maxPathSum(matrix);
        System.out.println("最大路径和为:"+maxSum);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

3.在一个遥远的银河中，有N个星球（编号从1到N)，这些星球之间通过星际门进行连接。每个星际门都连接两个星球，并旦可以双向通行。
每个星际门的开启需要消耗一定的能量，这个能量由星际门上的数字表示。每个星际门上的数字都是唯一的。
现在，由于某种原因，所有的星际门都处于 关闭状态。作为一个探索者，你的任务是找出一种方式，开启最少的星际门，使得所有的星球都至少通过一个开启的星际门与其他星球连接。
给你一些可连接的选项 connections，其中connections[i] = [Xi, Yi, Mi] 表示星球 Xi和星球Yi之间可以开启一个星际门工并消耗 Mi 能量。
计算联通所有星球所需的最小能量消耗。如果无法联通所有星球，则输出-1。

import java.util.*;
import java.util.Arrays;
public class Solution1 {
    public static int minimumEnergyRequired(int N,int[][] connections){
        Arrays.sort(connections,(a,b)->a[2]-b[2]);
        int[] parent = new int[N+1];
        //parent[i] 存储了元素i的父节点的编号，
        // 如果 parent[i] 的值为-1，表示元素i是自身所在集合的根节点。
        Arrays.fill(parent,-1);
        int minEnergy = 0;
        int numEdges = 0;
        for(int[] connection:connections){
            int front = connection[0];
            int to = connection[1];
            int energy = connection[2];

            int rootFrom = findRoot(parent,front);
            int rootTo = findRoot(parent, to);

            if(rootFrom!=rootTo){
                parent[rootFrom] = rootTo;
                minEnergy += energy;
                numEdges++;//已经合并的星际门数量
                if(numEdges==N-1){
                    return minEnergy;
                }
            }
        }
        return -1;
    }
    //它的作用是查找某个节点在并查集中所属的集合的根节点，并在查找过程中进行路径压缩，
    private static int findRoot(int[] parent,int node){
        if(parent[node] == -1){
            return node;
        }
        parent[node] = findRoot(parent,parent[node]);//这一步是路径压缩的关键，它将节点 node 的父节点直接设置为根节点，
        // 从而优化后续的查找操作。
        return parent[node];
    }
    public static void main(String[] args) {
        int N=4;
        int[][] connections = {
                {1,2,5},
                {1,3,6},
                {2,3,1},
                {3,4,2},
                {2,4,3},
        };
        int result = minimumEnergyRequired(N,connections);
        System.out.println("最小能量消耗为:"+result);
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55