笔试时间：2025年9月15日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：前置课程

为了毕业你需要选择n门课程，这n门课程中存在一定的依赖关系，例如想要完成B课程，必须先完成A课程。请你找出一个可以完成全部课程的顺序，如果无论如何选择都无法完成全部课程则返回空数组。

依赖关系以如下方式输入：[[2,1],[3,2]]。即要完成课程2，必须先完成1，要完成课程3，必须先完成课程2。答案[1,2,3]即可。但也可能出现类似[[2,1],[1,2]]，要完成课程2，必须先完成1，要完成课程1，必须先完成课程2，则无解，返回一个空数组即可。

数据范围：1≤n<2000，依赖关系的数量满足0≤m≤n*(n-1)，保证不会有一组一模一样的依赖关系。

输入描述

依赖关系数组和课程总数

输出描述

可以完成所有课程的顺序数组，如果无法完成则返回空数组

样例输入

[[1,0],[2,1]]

样例输出

[0,1,2]

参考题解

解题思路：

本题是经典的拓扑排序问题。将课程依赖关系建模为有向图，使用Kahn算法：

1. 构建邻接表表示依赖关系，统计每门课程的入度
2. 将入度为0的课程加入队列
3. 依次处理队列中的课程，将其加入结果数组，并减少其后继课程的入度
4. 若后继课程入度变为0则加入队列
5. 最终若结果数组长度等于课程总数，说明无环可完成所有课程；否则返回空数组

C++：

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        
        for (auto& prerequisite : prerequisites) {
            int course = prerequisite[0];
            int preCourse = prerequisite[1];
            graph[preCourse].push_back(course);
            inDegree[course]++;
        }
        
        // 队列存储入度为0的节点
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int currCourse = q.front();
            q.pop();
            result.push_back(currCourse);
            
            for (int nextCourse : graph[currCourse]) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    q.push(nextCourse);
                }
            }
        }
        
        return result.size() == numCourses ? result : vector<int>();
    }
};

Java：

import java.util.*;

public class CourseSchedule {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 构建邻接表表示图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 入度数组
        int[] inDegree = new int[numCourses];
        
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int preCourse = prerequisite[1];
            graph.get(preCourse).add(course);
            inDegree[course]++;
        }
        
        // 队列，用于存储入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] result = new int[numCourses];
        int index = 0;
        
        while (!queue.isEmpty()) {
            int currCourse = qu