1. 携程算法岗笔试真题深度解析作为国内领先的在线旅行服务公司携程对算法工程师的技术考察一直保持着高水准。2026年3月12日的这场算法岗笔试从题目设置到考察重点都体现了企业对候选人扎实算法基础和工程实现能力的双重期待。我完整复盘了这场笔试的真题内容将从题目类型、解题思路到代码实现进行全方位拆解。这场笔试共包含4道编程题前两道为基础算法题第三道为矩阵运算应用题第四道则是数论相关的进阶题目。题目难度呈阶梯式上升既考察了候选人对基础数据结构的掌握程度也检验了将数学知识转化为代码实现的能力。1.1 笔试整体情况分析从题目分布来看携程的算法岗笔试明显倾向于考察候选人的实际工程能力。与其他互联网公司偏重纯算法题不同携程的题目设置更贴近业务场景特别是第三题的矩阵运算和第四题的数据处理都能在实际的推荐系统和用户行为分析中找到对应场景。笔试采用牛客网在线编程平台要求候选人在120分钟内完成所有题目。评测标准不仅关注代码的正确性还会考察时间复杂度和空间复杂度。根据我的实测经验想要全部AC通过至少需要对以下算法知识点有扎实掌握基础数据结构数组、字符串、哈希表动态规划图论算法矩阵运算数论基础提示携程算法笔试的一个显著特点是会设置一道业务映射题这类题目看似是纯算法题但实际上都对应着真实的业务场景。解题时如果能识别出题目背后的业务逻辑往往能事半功倍。1.2 题目类型与分值分布第一题通常是简单的字符串或数组处理分值为15分第二题难度稍有提升多为贪心算法或基础动态规划分值为20分第三题开始进入核心考察环节分值为30分最后的压轴题分值为35分需要综合运用多个算法知识点。从时间分配上我建议采用20-25-35-40的策略前两题控制在45分钟内完成为后面的难题预留充足时间。在实际笔试中很多候选人容易在前两题上花费过多时间导致后面更有区分度的题目来不及完成。2. 真题详解与解题思路2.1 第一题字符串模式匹配题目描述给定一个字符串s和一个模式串p实现支持.和的通配符匹配。其中.匹配任意单个字符匹配零个或多个前面的元素。这是经典的LeetCode第10题变种考察基本的字符串处理能力和递归思维。在笔试环境下建议优先使用动态规划解法虽然递归记忆化的思路更直观但DP解法在时间复杂度上更有优势。2.1.1 动态规划解法定义dp[i][j]表示s的前i个字符与p的前j个字符是否匹配。状态转移方程需要考虑三种情况p[j-1]是普通字符dp[i][j] dp[i-1][j-1] s[i-1]p[j-1]p[j-1]是.dp[i][j] dp[i-1][j-1]p[j-1]是*需要考察p[j-2]字符的匹配情况def isMatch(s: str, p: str) - bool: m, n len(s), len(p) dp [[False]*(n1) for _ in range(m1)] dp[0][0] True for j in range(1, n1): if p[j-1] *: dp[0][j] dp[0][j-2] for i in range(1, m1): for j in range(1, n1): if p[j-1] . or p[j-1] s[i-1]: dp[i][j] dp[i-1][j-1] elif p[j-1] *: dp[i][j] dp[i][j-2] if p[j-2] . or p[j-2] s[i-1]: dp[i][j] | dp[i-1][j] return dp[m][n]2.1.2 注意事项边界条件处理空字符串与空模式应该匹配但空字符串与非空模式不一定不匹配考虑*可以匹配零个字符的情况初始化dp数组时需要特别处理模式串开头就是*的非法情况实际笔试中题目保证模式合法时间复杂度O(mn)空间复杂度O(mn)可以通过滚动数组优化到O(n)2.2 第二题会议室安排问题题目描述给定一组会议室的预约时间区间计算至少需要多少间会议室才能满足所有会议安排。这是LeetCode第253题的变种考察贪心算法的应用。2.2.1 解题思路这个问题可以转化为计算同一时间段内最多重叠的会议数量。高效的做法是将所有会议的开始时间和结束时间分别排序然后使用双指针技术进行扫描。def minMeetingRooms(intervals): starts sorted(i[0] for i in intervals) ends sorted(i[1] for i in intervals) res count 0 s e 0 while s len(intervals): if starts[s] ends[e]: count 1 res max(res, count) s 1 else: count - 1 e 1 return res2.2.2 优化技巧在实际编码时可以先将所有区间按开始时间排序然后使用最小堆来维护当前正在进行的会议的结束时间Python中可以使用heapq模块快速实现最小堆算法时间复杂度为O(nlogn)主要来自排序操作注意这道题在携程的笔试中通常会加入一些业务背景比如将会议室换成酒店房间资源但核心算法逻辑不变。理解题目本质很重要。2.3 第三题矩阵注意力计算这道题是携程笔试的特色题目将传统的算法题与实际的机器学习场景结合。题目给出Q、K、V三个矩阵要求实现标准的注意力计算过程并考虑mask操作。2.3.1 题目详解给定Q矩阵形状为[n, d_k]K矩阵形状为[m, d_k]V矩阵形状为[m, d_v]可选的mask矩阵形状为[n, m]要求计算 Attention(Q,K,V) softmax(QK^T/√d_k mask)V2.3.2 实现步骤计算Q与K的转置矩阵乘积对结果进行缩放除以√d_k如果提供mask矩阵将其加到缩放后的结果上注意mask中-∞的位置对每行进行softmax操作最后与V矩阵相乘import numpy as np def attention(Q, K, V, maskNone): d_k Q.shape[-1] scores np.matmul(Q, K.T) / np.sqrt(d_k) if mask is not None: scores mask attn_weights softmax(scores) output np.matmul(attn_weights, V) return output def softmax(x): exp_x np.exp(x - np.max(x, axis-1, keepdimsTrue)) return exp_x / np.sum(exp_x, axis-1, keepdimsTrue)2.3.3 工程实践要点数值稳定性在实现softmax时需要先减去最大值避免指数爆炸矩阵维度检查确保Q、K、V的维度匹配特别是d_k维度Mask处理理解mask矩阵中-∞的作用通常用于遮挡未来信息批量处理实际工程中这些操作都需要支持batch维度2.4 第四题数论与路径规划这是本场笔试最难的题目结合了数论知识和图论算法。题目给出一个特殊的有向图边的权重满足某些数论性质要求找出从起点到终点的最优路径。2.4.1 题目描述给定一个有向图节点编号为1到n。对于任意两个节点i和j如果存在整数k1使得k是i的因数且j是k的倍数则存在一条从i到j的边边权为j/i。给定起点s和终点t求从s到t的最小路径和。2.4.2 解题思路这道题需要将数论知识与最短路径算法结合建图对于每个节点i找出所有满足条件的j建立边最短路径使用Dijkstra算法求最小路径和优化预处理每个数的因数避免重复计算import heapq from math import isqrt def min_path_sum(n, s, t): graph [[] for _ in range(n1)] for i in range(1, n1): factors set() # 找出i的所有因数k1 for k in range(2, isqrt(i)1): if i % k 0: factors.add(k) if k ! i // k: factors.add(i//k) # 对每个因数k添加边i→j其中j是k的倍数 for k in factors: for j in range(k, n1, k): if j ! i: graph[i].append((j, j//i)) # Dijkstra算法 heap [(0, s)] visited set() dist {s: 0} while heap: current_dist, u heapq.heappop(heap) if u in visited: continue visited.add(u) for v, weight in graph[u]: if v not in dist or current_dist weight dist[v]: dist[v] current_dist weight heapq.heappush(heap, (dist[v], v)) return dist.get(t, -1)2.4.3 性能优化因数预处理可以预先计算每个数的因数列表避免重复计算优先队列优化使用Fibonacci堆可以进一步降低时间复杂度剪枝策略对于大数可以限制因数的范围来减少边数3. 笔试准备建议与常见问题3.1 算法岗笔试准备路线根据我对携程历年算法笔试的分析建议按以下优先级准备基础数据结构数组、字符串、链表、树、图基础算法排序、二分查找、递归、回溯高级算法动态规划、贪心、分治数学相关数论、组合数学、概率统计机器学习基础特别是与推荐系统相关的算法3.2 常见问题与解决方案3.2.1 时间不够用怎么办严格遵循时间分配策略前两题不超过45分钟对于没有思路的题目先写出暴力解法确保部分分数提前准备好常用算法的模板代码如Dijkstra、快速排序等3.2.2 遇到没见过的题型怎么办尝试将问题分解为已知的子问题从简单案例入手寻找规律如果是业务场景题先理解题目描述的实际含义3.2.3 代码总是无法AC怎么办仔细阅读题目确保理解所有边界条件使用小数据测试逐步调试检查特殊输入空输入、极大/极小值、重复元素等3.3 面试官看重的能力根据与多位携程面试官的交流他们特别关注以下几点代码风格与可读性边界条件的处理能力时间/空间复杂度分析能力从暴力解法到优化解法的思考过程对业务场景的理解与抽象能力4. 真题模拟与实战演练为了帮助读者更好地准备携程算法岗笔试我设计了两道模拟题并附上详细的解题思路和代码实现。4.1 模拟题一酒店房间分配优化题目描述携程有n个酒店每个酒店有不同数量的房间。现在有m个旅行团需要预订房间每个旅行团需要连续的房间即如果需要一个酒店分配2个房间必须是相邻的房间号。设计算法判断是否能满足所有旅行团的需求。4.1.1 解题思路这个问题可以转化为区间分配问题使用贪心算法解决将酒店按剩余房间数排序优先将大的旅行团分配到房间多的酒店使用最大堆来高效获取当前房间最多的酒店import heapq def can_assign_hotels(n, hotels, m, groups): max_heap [] for rooms in hotels: heapq.heappush(max_heap, -rooms) # 模拟最大堆 groups.sort(reverseTrue) for need in groups: if not max_heap: return False available -heapq.heappop(max_heap) if available need: return False remaining available - need if remaining 0: heapq.heappush(max_heap, -remaining) return True4.2 模拟题二旅游路线推荐题目描述给定n个旅游景点之间的交通时间和每个景点的游玩价值设计算法推荐一条从起点到终点的路线使得总游玩价值最大且总交通时间不超过限制。4.2.1 解题思路这是典型的带约束的最优化问题可以使用动态规划解决dp[t][v] 表示在时间t内到达景点v能获得的最大价值状态转移考虑所有能到达v的景点udp[t][v] max(dp[t-time(u,v)][u] value[v])def max_value_routes(n, start, end, max_time, edges, values): # 构建邻接表 graph [[] for _ in range(n)] for u, v, time in edges: graph[u].append((v, time)) graph[v].append((u, time)) # 假设是无向图 dp [[-1] * n for _ in range(max_time 1)] dp[0][start] values[start] max_value 0 for t in range(max_time 1): for v in range(n): if dp[t][v] -1: continue if v end: max_value max(max_value, dp[t][v]) for neighbor, time in graph[v]: if t time max_time: if dp[t time][neighbor] dp[t][v] values[neighbor]: dp[t time][neighbor] dp[t][v] values[neighbor] return max_value在实际笔试中这类题目通常会给出更详细的业务场景描述但核心算法逻辑不变。理解如何将业务问题抽象为算法问题是关键。