联想2025秋招算法笔试真题解析：KMP、并查集与堆排序考点全盘点

每年八月底到十月初，秋招战线拉得最长的一批公司里，联想绝对排得上号。我这两年帮师弟师妹改简历、做模拟面试，前前后后接触了不少联想2025届秋招的算法岗笔试题，自己也把能找到的真题和面经整理了一遍。说实话，联想的算法编程题不像互联网大厂那样追求“奇技淫巧”，它更看重基础功底和工程思维的扎实程度，题型也相对固定。这篇文章我就把整理出来的题目集合、考点分析和刷题思路一次性讲清楚，整篇都是干货，不掺水。

需要说明的是，这里整理的题目来源于2025届秋招的公开面经、牛客网博主分享以及我自己的模拟测试，不是官方题库，但考点的覆盖度和题目风格是高度接近的。无论你是准备联想，还是顺带投其他硬件厂商、智能制造类公司，这套题都可以直接用。

1. 联想2025秋招算法题到底考什么

1.1 笔试题型构成与分值分布

联想的技术笔试一般分为两到三个部分，算法编程题是绝对的大头，通常占比在50%到60%之间。我统计了下近两年联想各岗位的笔试反馈，发现它的题型构成基本稳定：

单选和多选部分主要考察基础理论，比如排序算法的时间复杂度比较、哈希冲突的处理方式、二叉树的遍历序列推导、进程和线程的区别、TCP三次握手的状态变化等。这些题目的难度介于校招常规题和考研408之间，只要基础扎实，基本不用花太多时间。

真正拉分的是后面的编程题。联想的编程题有一个比较明显的特点：不会一上来就给你一个特别复杂的场景题，而是先来一道“热身题”，再做一道“进阶题”，最后可能有一道“区分度题”。热身题通常是字符串处理或简单模拟，进阶题是常见的动态规划或贪心，区分度题则是图论、KMP、状态压缩这类需要一定算法积累的题目。

1.2 核心考点覆盖范围

从题目集合来看，联想算法笔试的考点主要集中在以下几个方面，我按出现频率排了个序：

第一梯队（必考）：字符串处理、数组和链表操作、二叉树遍历、排序算法、动态规划的基础模型（背包、最长公共子序列、最长递增子序列）。

第二梯队（高频）：哈希表应用、双指针、滑动窗口、贪心算法、图的深度和广度优先遍历、最小生成树和最短路算法。

第三梯队（进阶）：KMP算法、堆的高级应用、并查集、二分图匹配、拓扑排序、状态压缩DP。

单从这张表看，联想考察的算法范围并不局限于互联网公司常考的“八股算法”，它对一些工程上常用的算法同样有偏好。比如KMP算法中的next数组推导、并查集在连通性问题中的应用，这些在联想笔试题里出现的频率明显高于其他公司。这可能和联想本身是做硬件和系统集成的有关，它的业务场景里有大量字符串匹配、设备连通性检测、路径规划这类实际问题。

1.3 面试手撕与笔试机考的双重准备

联想的面试环节同样包含手撕代码，这和笔试的机考风格有所不同。机考更看重你能不能在一个半小时内写出可运行的代码，而面试手撕更看重你现场的分析能力和代码风格。我在整理题目集合的过程中发现，很多在笔试里出现的题目，会在面试环节以变形题的方式再次出现。

比如笔试里考了“最长公共子序列的长度”，面试官在面试时就可能追问“如果两个字符串的长度差异很大，怎么优化空间复杂度”。又比如笔试里考了“手写快排”，面试时就会让你分析“为什么快排在有序数组上表现差，怎么优化”。

所以我的建议是，不能只做题，要把每一道题背后的原理吃透。这道题为什么用这个算法，时间复杂度为什么是这个量级，空间上能不能再优化，这些是面试官真正想听到的东西。

2. 编程语言选型与模板库准备

2.1 C++、Java、Python三选一怎么定

联想笔试系统支持的语言比一般互联网公司更全，C++、Java、Python、Go基本都在列表里。但这里我强烈建议，除非你只会Python且已经熟练到能处理大输入量的程度，否则优先选择C++或Java。

原因很简单：联想的笔试编程题有些时间卡得比较紧，有的题目数据范围给到了10的5次方甚至10的6次方。如果是O(n log n)级别的算法，Python还能应付，但如果题目本身要求常数级优化，Python很容易在最后一个数据点超时。我自己统计过，联想的编程题里大概有30%的题目用Python写会非常勉强，除非你能保证自己的代码没有任何多余操作。

如果你选择C++，有几个常用库要提前熟悉：vector、unordered_map、map、set、priority_queue、deque、algorithm头文件里的sort、reverse、unique、lower_bound等。这些容器和函数的熟练使用能帮你省下大量写基础数据结构的时间。

选择Java的同学则要重点掌握HashMap、TreeMap、PriorityQueue、ArrayList、LinkedList、Arrays.sort、Collections.sort等常用类和静态方法。

2.2 必须达到“肌肉记忆”的几套代码模板

很多人觉得算法题考的是“想得出来”，但真正上了考场你会发现，考的是“写得快”和“写得对”。以下几种代码结构我建议你在考前全部手写过至少五遍，做到闭着眼睛都能敲出来：

快速排序和归并排序。这两个排序算法在单选和编程里都有可能出现，而且归并排序的代码框架还能用来解决逆序对问题。

二分查找的标准写法。注意边界条件是left <= right还是left < right，查找左边界和右边界时分别怎么写。很多人栽在二分查找的细节上，就是因为平时只写标准版本，没有专门练过边界版本。

并查集的完整实现。包括路径压缩的迭代写法和按秩合并。这个数据结构代码量不大，但考场上临时写很容易漏掉初始化步骤。

二叉树的前序、中序、后序、层序遍历，各写递归和迭代两个版本。迭代版本要配合栈和队列，能解决很多需要记录层级的题目。

背包问题的一维和二维DP模板。01背包、完全背包、多重背包的状态转移方程分别是什么，滚动数组怎么优化。

Dijkstra算法的堆优化版本和SPFA。图论的题目在联想笔试里出现的频率不低，priority_queue加邻接表的写法要非常熟练。

我强烈建议把这些模板整理成一个本地的代码库，考前每天默写一遍。这不是浪费时间，而是确保你在考场上的前几道题能用“肌肉记忆”快速解决，把时间留给后面的难题。

2.3 输入输出处理的常见坑

联想的笔试系统输入输出和牛客网的风格比较像，意味着很多题目不会像力扣那样给你封装好函数接口，而是要求你自己处理标准输入。有些同学平时刷题只刷力扣，到了联想的笔试系统上反而栽了跟头。

常见的问题有几个。第一个是读取含空格的字符串时，cin >> s只能读到第一个空格前的部分，需要用到getline。第二个是事先不知道数组长度，要通过第一行输入读入n，再循环读入n个数。第三个是输出格式要求“空格分隔，末尾无多余空格”，这个细节很多人会漏掉，最后被判输出格式错误。

我建议你在平时练习时就用牛客网的笔试模式，而不是只用力扣的代码模式。把输入输出的处理变成条件反射，考场上才不会慌。

3. 经典真题手把手解析

3.1 KMP算法中的next数组推导

联想对KMP算法确实有偏爱，这个在热搜词里也能看出来。前一阵牛客网上一道关于模式串p="abacaba"的next数组推导题传得很火，2025届联想笔试的选择题部分还真出了类似题，只不过把模式串换成了别的。这道题的核心不是让考生背KMP模版，而是考察对next数组概念的理解是否正确。

先明确next数组的定义：next[i]表示模式串前i个字符组成的子串中，最长相等前缀和后缀的长度。注意这里的“前缀”和“后缀”都不包含整个子串本身。以p="abacaba"为例，我们从头开始推导：

• 子串"a"：前缀和后缀都不包含自身，所以没有相等的前后缀，next[1]=0。
• 子串"ab"：前缀有"a"，后缀有"b"，不相等，next[2]=0。
• 子串"aba"：前缀"a"、"ab"，后缀"a"、"ba"，最长相等的是"a"，长度为1，next[3]=1。
• 子串"abac"：分别看前缀和后缀，没有相等的情况，next[4]=0。
• 子串"abaca"：前缀"a"、"ab"、"aba"、"abac"，后缀"a"、"ca"、"aca"、"baca"，只有"a"相等，next[5]=1。
• 子串"abacab"：前缀里有"ab"，后缀里也有"ab"，长度为2，next[6]=2。
• 子串"abacaba"：前缀"a"、"ab"、"aba"、"abac"、"abaca"、"abacab"，后缀"a"、"ba"、"aba"、"caba"、"acaba"、"bacaba"，最长的相等前后缀是"aba"，长度为3，next[7]=3。

最终得到next数组为0 0 1 0 1 2 3。这里有一个容易混淆的细节：有的教材把next数组定义为“匹配失败时模式串指针回退的位置”，也就是把数组整体右移一位并令next[0]=-1，那会出现另一套值。所以在考场上一定要先看清楚题目对next数组的定义，是“最长相等前后缀长度”还是“回退位置”，这两个定义在实际使用中相差很多，比如前者在匹配失败时模式串指针通过i = next[i - 1]更新，后者则直接将指针回退到next[i]。

如果笔试遇到了KMP选择题，最快的验证方法是随便找一个字符串跑一遍暴力匹配的过程，判断当前这个位置如果失配，模式串指针到底应该跳到哪。不要死记硬背模板，理解定义比记住代码值钱得多。

3.2 手写堆排序的完整步骤

堆排序在联想笔试里属于大热门，因为它既能考选择题里的复杂度分析，又能考编程题里的手写实现。一般在编程题里，手写堆排序不会直接考“把数组排成有序”，而是会换成“找第K大的数”“求前K个最小元素”这种变体，但核心都离不开堆的调整。

堆排序的思路分两步：先建堆，再排序。建堆时，对数组从最后一个非叶子节点开始，依次做向下调整（sift down）。最后一个非叶子节点的下标是n/2 - 1（数组从0开始）。向下调整的过程是，把当前节点和它的左右孩子比较，如果孩子节点更大（大顶堆）就交换，然后继续向下调整，直到满足堆的性质。

建好堆后，堆顶就是数组的最大值。把堆顶和数组末尾的元素交换，然后数组长度减1，再对新的堆顶做一次向下调整，重复这个过程就得到了升序数组。因为大顶堆弹出的是最大值，放到数组末尾，所以升序排序用大顶堆，降序排序用小顶堆。

C++参考代码如下：

void siftDown(vector<int>& nums, int idx, int len) { while (idx * 2 + 1 < len) { int child = idx * 2 + 1; if (child + 1 < len && nums[child + 1] > nums[child]) { child++; } if (nums[child] > nums[idx]) { swap(nums[child], nums[idx]); idx = child; } else { break; } } } void heapSort(vector<int>& nums) { int n = nums.size(); for (int i = n / 2 - 1; i >= 0; i--) { siftDown(nums, i, n); } for (int i = n - 1; i > 0; i--) { swap(nums[0], nums[i]); siftDown(nums, 0, i); } }

这个实现有几个容易踩坑的地方。第一个是在siftDown里，循环终止条件是idx * 2 + 1 < len，不是idx < len，因为如果当前节点已经没有了左孩子，说明它已经是叶子节点，不需要再调整。第二个是在找左右孩子中最大的时候，不能先判断左孩子再单独判断右孩子，而应该先假设左孩子更大，再比较右孩子是否超过左孩子。第三个是排序阶段的循环边界，每轮交换后数组的有效长度减1，所以是siftDown(nums, 0, i)而不是siftDown(nums, 0, n)。

如果你选择用Java写，思路完全一致，只是把vector换成int[]，把swap写成手动的三步交换。

3.3 动态规划典型题：01背包与最长公共子序列

动态规划在联想笔试编程题里基本是必考的，但联想的DP题有一个特点，它不爱考特别偏的状态设计，更爱考经典模型的变形。我自己在2025届秋招期间整理到的联想笔试真题里，至少出现了三次01背包的变体题，还有一次是求两个字符串的最长公共子序列长度。

01背包的经典描述是：有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，问最多能装多少价值的物品。状态转移方程是dp[j] = max(dp[j], dp[j - w[i]] + v[i])，但要注意一维数组更新时必须从大到小遍历j，否则前面更新的状态会影响后面的计算，相当于同一个物品被装了多次。

联想喜欢在这个基础上做变形，比如“如果物品之间还有互斥关系怎么办”“每个物品可以选择装1件或2件怎么办”。前者需要引入分组背包的思想，后者需要多开一维状态记录数量。但不管怎么变，核心还是要理解“背包容量j”和“决策第i个物品是否装入”这两层循环的本质。

最长公共子序列（LCS）则是考虑dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列长度。如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这道题常考的空间优化版本是用滚动数组把二维降到一维，但要注意降维后状态更新时要处理好依赖关系，稍有不慎就会覆盖掉还没使用的数据。

联想有时候还会把LCS和字符串拼接、回文判断结合起来，比如“给两个字符串，判断其中一个是否能通过删除若干字符得到另一个”，这其实就是判断短串是否是长串的子序列，可以用双指针解决，不一定要上DP。考试时先想清楚是不是存在更简单的解法，再决定要不要套模板。

3.4 图论算法：从Dijkstra到最小生成树

图论的题目在联想的编程题中出镜率也不低。原因不难理解，联想有大量的设备组网、智能工厂路径规划、供应链管理业务，这些场景天然和图算法绑定。

Dijkstra算法求单源最短路是出现频次最高的。如果是稀疏图（顶点多、边少），一定要用邻接表加优先队列实现，时间复杂度是O((V+E)logV)。如果用邻接矩阵加朴素遍历，复杂度是O(V^2)，顶点数一旦超过一万就会超时。我在真题里看到过一道“从城市A到城市B的最短时间，中间每个城市有等待时间”的题，本质上就是Dijkstra，只需要把等待时间加到节点的距离上即可。

最小生成树考的频率要低一点，但也不是没有。Prim算法适合稠密图，Kruskal算法适合稀疏图，后者因为要用到并查集，所以经常和并查集一起考。如果你对并查集不熟悉，最小生成树的编程题会写起来特别费劲。这道题还有一个常见的坑：“图中可能有重边，两个节点之间有多条边时只保留最短的一条”，如果你用邻接矩阵存图，直接取min就行，但如果你用邻接表，就必须在插入时判断。

另外力扣和牛客上的模板题往往给的是“编号从1到n”的节点，但有些笔试题目里的节点编号可能从0开始，也可能不是连续的。读题时一定要先看清是“1-indexed”还是“0-indexed”，这种低级错误一旦出现，整个程序都会跑偏，而且很难Debug出来。

3.5 进阶难题模拟：粒子群、模拟退火与二分图

在整理联想热搜词的时候，我发现“粒子群算法原理”“模拟退火算法”“二分图hk算法”这类词的热度很高，这些也确实在联想2025届的某些岗位（尤其是AI算法岗和机器人算法岗）的笔面试中出现过。不过要注意，这些算法在笔试编程题里很少让你裸写，更多是在选择题或面试问答环节出现。

粒子群算法（PSO）的原理要抓住三个核心要素：粒子位置、粒子速度、以及两个最优位置（个体最优pbest和群体最优gbest）。每次迭代时，粒子根据v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x)更新速度，再用新速度更新位置。这里的w是惯性权重，c1和c2是加速系数，r1和r2是[0,1]之间的随机数。面试时如果能说清楚“惯性权重越大，全局搜索能力越强；越小，局部搜索能力越强”，基本就能过。

模拟退火算法的关键是“以一定概率接受更差的解”，这个概率是exp(-delta/T)，其中delta是当前解和目标解的差值，T是当前温度。温度随着迭代次数不断下降，接受差解的概率也就越来越小。面试官可能会追问“温度下降策略有哪些”，常见的有线性降温、指数降温（T = alpha * T，alpha一般取0.9到0.99）等。

二分图匹配里，匈牙利算法（HK算法是优化版）在“任务分配”“资源调度”类场景中出现频率最高。核心思想是“增广路”，如果能找到一条增广路，那么匹配数就加1。这个算法不复杂，但理解起来需要多画几张图，我在后面专门列一道题来演示。

总而言之一句话：这些“高级算法”不要求你考前临时抱佛脚去狂刷，但基本思想、适用场景、核心参数的物理意义，你得能说出来。联想面试官特别看重“你这个算法能解决我们实际业务里的什么问题”，而不是“你能不能默写伪代码”。

4. 现场笔试的实战策略与避坑清单

4.1 拿到题目后的第一件事：别急着写代码

很多同学上了笔试系统，看到第一道编程题有点思路就开始噼里啪啦敲键盘，这是大忌。联想的笔试系统只保留最后一次提交的代码，不会自动保存中间版本，所以你一旦敲到一半发现思路错了，前面的时间就都浪费了。

我的建议是，拿到所有编程题后，先把每一道题都读一遍，在草稿纸上写下大致的思路、数据范围、算法复杂度。数据范围在10^4以下的题目可能O(n^2)能过，10^5以上基本就得O(nlogn)或O(n)。把这些判断写清楚再动手，比你盲目做一道看一道省时间得多。

时间分配上，如果一共4道编程题，前两道热身和常规题应该在30到40分钟内搞定，后面两道难题每道留20分钟左右。如果某一道题卡了15分钟以上还没边儿，果断先跳过去做后面的。联想笔试的计分规则一般不是按通过率算分，是通过一个test case得一个test case的分，所以即使是部分正确，把代码提交上去也能拿到一部分分数，千万不能留白。

4.2 高频低级错误整理

我把这些年看到同学们在笔试中出现频率最高的低级错误整理成了一个表格，考前花三分钟扫一眼，能帮你避免很多不必要的失分。

还有一个特别隐蔽的问题：很多题目要求输出对某个大质数（比如10^9+7）取模后的结果，但如果你在中间计算过程中才取模，而之前已经发生了溢出，那取模也没有意义。正确做法是每次累加或相乘后立即取模。

4.3 联想笔试特有的“隐藏规则”

联想的笔试系统和某些公司的系统不一样，有几个“隐藏规则”是我通过多次实测和面经总结出来的，这里专门列一下，免得后面的人再踩坑。

第一，编程题允许多种语言提交，但同一道题的C++代码时间限制可能只有1秒，而Python可能放宽到3秒。不要因为Python代码短就无脑选Python，如果你的算法在C++里1秒能过，在Python里还是有超时风险，最好在本地用大数据量自测一次。

第二，联想的笔试系统在代码编辑器中不会自动提示语法错误，所以你在本地IDE里编译通过之后，再复制到笔试系统时，一定要检查是否把#include <iostream>、using namespace std之类的头文件和声明一起复制进去了。有同学就是只复制了函数体，导致系统判编译错误，白白丢分。

第三，部分岗位的笔试会加一道系统设计题或场景题，这不是编程题，而是要求你用文字描述系统架构或算法的部署方案。这种题分值不低，但很多同学不知道，技术栈还是按纯算法来准备，结果那一整道题空白。如果你投的是联想的算法工程化岗位，务必提前准备一下“某个算法在工业场景中如何落地”这类问题。

5. 检查清单与Debug方法

5.1 提交前的5分钟自查清单

我给自己定了规矩：代码写完之后，不急着点提交，先花5分钟做一遍自查。别小看这个习惯，它能帮你抓住至少30%的低级错误。

自查的第一步是重新读一遍题目，把题目中的样例输入和期望输出拿出来，手动跑一遍你的代码，确认逻辑正确。第二步是检查所有数组下标的边界，重点看“最后一个元素”和“空数组”这两个极端情况。第三步是测试n=1或输入只有一个节点的情况，很多代码在处理最小规模数据时会暴露出变量初始化的错误。第四步是检查输出格式，包括空格、换行、大小写、小数位数，尤其是浮点数输出时保留几位小数。第五步是在脑子里模拟一下大数据量的情况，估算时间和空间是否在限制内。

如果在最后的5分钟里发现了一个问题，先判断问题的严重程度。如果不影响核心逻辑，只是输出格式的小瑕疵，那么果断修改后提交。如果发现自己把整个算法都想错了，那就不要挣扎了，把当前已经写出来的代码尽量改成暴力解法或部分优化版本，至少保证一部分测试用例能通过。

5.2 高效调试技巧：不要用“人脑编译”

有些同学在笔试时遇到Bug，会盯着屏幕一行一行地“人脑编译”，试图通过阅读找出错误。这对于超过三十行的代码来说效率非常低。我的建议是直接用调试工具，或者快速在本地IDE里跑测试样例。

如果你用的C++，在本地调试时用cout打印关键中间变量是最高效的方式。比如检查排序后的数组、DP数组的状态转移过程、并查集的父节点数组等。找到哪一步的结果和预期不一致，就能反推出问题出在哪一行。Java可以用System.out.println，Python可以用print。

一个更有效的技巧是：在纸上列出关键状态的“预期变化表”，然后用调试输出逐一核对。例如在KMP匹配过程中，记录每次失配时模式串指针的移动轨迹，和手算的结果对比。如果手算都对不上，那代码必然有问题。

5.3 从真题复盘到知识体系构建

做完一套题之后，不要急着把代码关掉。我在每次笔试结束后，都会花至少半小时做复盘，把每道题目的题型、考点、自己的解法、标准解法和优化思路记录到一个表格里。秋招刷题量大，不整理成体系的话，过两周再看到相同类型的题还是会觉得陌生。

我习惯把题目按“字符串”、“数组与双指针”、“树”、“图”、“动态规划”、“数论与位运算”六大类整理。每一类下面记录遇到的变体题、常用技巧、复杂度分析方法。整理的时候会发现，联想的题目虽然在具体描述上千变万化，但核心的算法模型就是那二十来种。只要这些模型的代码模板烂熟于胸，不管遇到什么样的题干，都能很快映射到对应的解法上。

复盘还有一个作用：它能帮你认清自己的薄弱模块。如果你发现自己在“图论”这一类题目上的正确率明显偏低，那就说明该集中精力补这块了，而不是继续漫无目的地刷题。秋招时间宝贵，针对性训练比全面铺开的效率高得多。

6. 一个完整的编程题实战演示

6.1 场景还原与思路分析

最后我用一道中等难度的题目，完整演示一遍联想想看到的解题思路和代码实现。这道题是我根据2025届联想笔试的真题改编的，考察的是并查集加图论判断。

题目描述大致如下：在一个仓库网络中有N个节点（编号0到N-1），每个节点代表一台设备，两个节点之间有直接的通信链路。现在有M条链路信息，每条信息包含两个节点的编号。要求判断这个网络中是否存在环路。如果存在环路，输出环路涉及的节点数量；如果不存在环路，输出0。

题目本质是“无向图判环”，最直接的解法是并查集。因为无向图判环有一个经典结论：在遍历边的过程中，如果一条边的两个端点已经在同一个集合中，那么加上这条边就形成了环。第一个出现这种情形的环，涉及的节点数量就是该集合的大小。

6.2 参考实现与关键代码

C++参考实现如下：

#include <iostream> #include <vector> using namespace std; vector<int> parent, sz; int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; // 路径压缩 x = parent[x]; } return x; } void unionSet(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) return; if (sz[ra] < sz[rb]) { parent[ra] = rb; sz[rb] += sz[ra]; } else { parent[rb] = ra; sz[ra] += sz[rb]; } } int main() { int N, M; cin >> N >> M; parent.resize(N); sz.resize(N, 1); for (int i = 0; i < N; i++) parent[i] = i; bool hasCycle = false; int cycleSize = 0; for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; int ru = find(u); int rv = find(v); if (ru == rv) { hasCycle = true; cycleSize = sz[ru]; break; } else { unionSet(ru, rv); } } if (hasCycle) { cout << cycleSize << endl; } else { cout << 0 << endl; } return 0; }

这段代码有几个关键点。第一个是路径压缩的写法parent[x] = parent[parent[x]]，它虽然不是最优的递归压缩，但能有效减少树的高度，而且配合循环写法不会出现栈溢出。第二个是按秩合并，这里用sz数组记录集合大小作为秩，每次把小的集合合并到大的集合里，保证树的深度控制在O(logN)。第三个是主循环里先找根再判环，这个顺序不能反，否则合并操作会破坏集合的正确性。

6.3 扩展思考：如果题目换一种问法

这道题如果继续深挖，联想面试官可能还会追问：如果这个图是带权图，判断是否有正权环怎么做；如果是判断有向图是否存在环，还能不能用并查集。第一个问题可以通过Bellman-Ford或SPFA来解，第二个问题则需要用拓扑排序，用并查集直接判断有向图的环是不成立的。

我在实际整理真题时发现，联想非常喜欢在一个基础模型上做“多步扩展”，所以准备笔试的时候不要只满足于能AC一道题，还要想想这道题和哪些知识点是连通的。这种思维方式对面试环节尤其重要，因为面试官很可能在你写完代码之后抛出这道题的变体，观察你能否举一反三。

7. 总结一下我在准备联想笔试过程中的几点体会

如果只让我说一条最重要的经验，那就是：联想算法笔试的核心不是“偏题怪题”，而是“基础扎实度”。它的题目难度曲线非常平滑，前50%的分数属于认真准备过的同学都能拿到的，后面20%到30%才是区分度所在。只要把常规的数据结构和算法模板练到肌肉记忆，再把KMP、并查集、堆排序这几个高频考点专门吃透，通过笔试的把握是很大的。

另外还有一点，就是在准备过程中不要只看联想的笔试，可以把它当作一个对其他硬件厂商和智能制造公司的通用准备。联想考查的KMP、并查集、堆排序、图的最短路径，这些在华为、小米、海康威视、大疆等公司的笔试里同样是高频考点。

最后再分享一个小技巧：秋招期间，把每次笔试的题目都记录下来，建立自己的错题本。不要只记录题解，要把“当时为什么会错”也写下来。我自己的错题本上写着最多的三个字是“没读题”，而不是“不会写”。把这两个字时刻记在脑子里，比多刷一百道题还有用。祝大家都顺利拿下心仪的offer。