✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

哔哩哔哩

题目一：软件模块依赖安装

1️⃣：构建有向图表示模块依赖关系，统计各节点入度

2️⃣：使用Kahn算法进行拓扑排序，处理循环依赖检测

3️⃣：输出安装顺序或空数组（存在循环依赖时）

难度：中等

这道题目考查图论中的拓扑排序算法。关键在于理解依赖关系构成的有向图，通过检测是否存在环来判断能否完成所有模块的安装。使用队列维护入度为0的节点，逐步删除边并更新入度，实现 O(n+m) 的高效解法。

题目二：DNA序列相似性分析

1️⃣：使用动态规划思想，定义状态为以某位置结尾的公共子串长度

2️⃣：通过滚动数组优化空间复杂度至 O(min(n,m))

3️⃣：在状态转移过程中记录最长公共子串位置信息

难度：中等

这道题目是经典的最长公共子串问题，需要理解动态规划的状态定义和转移。与最长公共子序列不同，子串要求字符连续出现。通过滚动数组技巧，在保证 O(n×m) 时间复杂度的同时，将空间复杂度优化到线性级别。

01. 软件模块依赖安装

问题描述

小兰正在为她的新项目配置开发环境，需要安装 个软件模块。这些模块之间存在复杂的依赖关系，例如要安装模块 ，必须先安装模块 。

由于系统资源限制，小兰希望找到一个合理的安装顺序，使得所有模块都能成功安装。如果模块间存在循环依赖（比如模块 依赖模块 ，而模块 又依赖模块 ），则无法完成安装，需要输出空的安装方案。

依赖关系以二维数组形式给出，例如 表示安装模块 需要先安装模块 ，安装模块 需要先安装模块 。模块编号从 开始。

输入格式

输入为一行，包含依赖关系数组和模块总数，格式为：依赖关系数组,模块数量

其中依赖关系数组的格式为 [[a1,b1],[a2,b2],...,[am,bm]]，表示安装模块 需要先安装模块 。

输出格式

输出一行，表示可行的安装顺序。

如果存在可行方案，输出格式为 [x1,x2,...,xn]，其中 为模块编号。

如果不存在可行方案（存在循环依赖），输出 []。

样例输入

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

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

样例输出

[0,1,2]

[0,1,2,3]

数据范围

• 

• 

• 保证不会有重复的依赖关系

题解

这道题本质上是一个有向图的拓扑排序问题。我们可以把每个模块看作图中的一个节点，依赖关系看作有向边。

如果图中存在环，说明有循环依赖，无解；如果不存在环，则可以通过拓扑排序找到一个合法的安装顺序。

解题思路：

1. 构建有向图，统计每个节点的入度
2. 将所有入度为0的节点加入队列（这些节点可以直接安装）
3. 不断从队列中取出节点，将其加入结果序列，并将其指向的所有节点的入度减1
4. 如果某个节点的入度减为0，则将其加入队列
5. 重复步骤3-4，直到队列为空

最后检查结果序列的长度是否等于模块总数。如果相等，说明所有模块都能安装；否则存在循环依赖。

时间复杂度为 ，其中 是模块数量， 是依赖关系数量。

参考代码

Python

import sys
input = lambda:sys.stdin.readline().strip()
from collections import deque

def solve():
    line = input()
    # 分离依赖列表和模块数量
    comma_pos = line.rfind(',')
    deps_str = line[:comma_pos]
    n = int(line[comma_pos + 1:])
    
    # 构建图和入度数组
    graph = [[] for _ in range(n)]
    in_deg = [0] * n
    
    # 解析依赖关系 [[1,0],[2,1]]
    nums = []
    cur_num = ""
    for char in deps_str:
        if char.isdigit():
            cur_num += char
        else:
            if cur_num:
                nums.append(int(cur_num))
                cur_num = ""
    if cur_num:
        nums.append(int(cur_num))
    
    # 建边：nums[i] -> nums[i+1] 表示要安装nums[i]需先安装nums[i+1]
    for i in range(0, len(nums), 2):
        if i + 1 < len(nums):
            a, b = nums[i], nums[i + 1]
            if a < n and b < n:
                graph[b].append(a)  # b指向a的边
                in_deg[a] += 1
    
    # Kahn算法拓扑排序
    queue = deque()
    for i in range(n):
        if in_deg[i] == 0:
            queue.append(i)
    
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # 移除该节点的所有出边
        for neighbor in graph[node]:
            in_deg[neighbor] -= 1
            if in_deg[neighbor] == 0:
                queue.append(neighbor)
    
    # 检查是否所有模块都能安装
    if len(result) == n:
        print("[" + ",".join(map(str, result)) + "]")
    else:
        print("[]")

solve()

Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string line;
    if (!getline(cin, line)) return 0;
    
    // 分离依赖关系和模块数量
    size_t pos = line.rfind(',');
    string deps = line.substr(0, pos);
    int n = stoi(line.substr(pos + 1));
    
    // 构建邻接表和入度数组
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    
    // 解析依赖关系数字
    vector<int> nums;
    string cur = "";
    for (char c : deps) {
        if (isdigit(c)) {
            cur += c;
        } else {
            if (!cur.empty()) {
                nums.push_back(stoi(cur));
                cur = "";
            }
        }
    }
    if (!cur.empty()) nums.push_back(stoi(cur));
    
    // 构建有向图
    for (size_t i = 0; i + 1 < nums.size(); i += 2) {
        int a = nums[i], b = nums[i + 1];
        if (a < n && b < n) {
            adj[b].push_back(a);  // b -> a 的边
            indeg[a]++;
        }
    }
    
    // 拓扑排序
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) q.push(i);
    }
    
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);
        
        // 删除u的所有出边
        for (int v : adj[u]) {
            if (--indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 输出结果
    if (topo.size() == n) {
        cout << "[";
        for (int i = 0; i < n; i++) {
            if (i > 0) cout << ",";
            cout << topo[i];
        }
        cout << "]\n";
    } else {
        cout << "[]\n";
    }
    
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        
        // 解析输入：分离依赖关系和模块数量
        int lastComma = line.lastIndexOf(',');
        String depsStr = line.substring(0, lastComma);
        int n = Integer.parseInt(line.substring(lastComma + 1));