携程春招技术岗笔试全解析：算法考点与避坑指南

携程2023年春招技术通用岗的第一批笔试我是在三月中旬参加的。当时投的是技术通用岗系统开放后直接约了最早一批想着趁题目还没怎么变难赶紧考掉。整场笔试下来最大的感受是题量不算夸张但覆盖面很广算法、数据库、网络、操作系统、智力题、情景选择都有而且部分题目的出题思路明显偏业务场景不是纯刷LeetCode就能应付的。这篇文章我就按当时的真实经历把笔试的结构、考点、解题思路和踩过的坑完整梳理一遍给后面要考携程技术岗的同学一个参考。1. 整体流程与笔试结构1.1 笔试批次怎么选开考前的准备携程的春招笔试是分批次进行的技术通用岗一般会安排多场你可以根据自己的时间在系统里选。我的建议是尽量选第一批原因有两个:第一第一批题目通常不会太难因为要照顾大部分考生后续批次往往会在算法和细节上加大难度第二早考完早点进入面试流程后续岗位如果还有调整也来得及拖到后面容易出现岗位已经排序完毕、只能进备选池的情况。笔试当天我提前半小时就上线调试环境了。携程用的是牛客网的系统摄像头全程开启页面会监控切屏行为。这里提醒一下一定不要切出浏览器去查资料系统对切屏次数非常敏感哪怕只是误触也会记录严重的话会直接判定作弊申诉都很麻烦。我当时把浏览器装好IDE用本地VS Code笔试环境里的代码编辑器能用但说实话不太好用我最终还是选择在本地IDE里调试确认无误后粘贴到系统里。开考后界面分左右两部分左侧是题目列表右侧是代码编辑区。支持的语言包括Java、C、Python、Go、JavaScript等主流语言C和Java的考生最多Python也不少。系统会自动保存代码但还是要自己留意提交按钮的位置别一股脑写完了忘记提交。1.2 题型分布与分值预估第一批笔试的总时长是120分钟题量在20道左右其中编程题1道单选/多选大约12道剩下的是不定项选择和情景题。具体分值官方没有明确公布但从题目数量来看编程题占比肯定最重至少要占30分以上其他的选择题分值相对平均但错误会倒扣分——这个很关键携程笔试的多选题是漏选不得分、错选倒扣分所以不确定的选项宁愿不选。我当时记录下来的题型分布大概是这样的题型数量主要考察内容预估分值占比编程题1道算法数据结构综合30%单选题8道计算机网络、操作系统、数据库25%多选题5道Java/C语言特性、Linux、分布式20%情景题4道排序算法、日志分析、方案设计15%智力题/其他2道逻辑推理、概率10%这不是官方数据是我当时考完根据各个题目的难度和花费时间推算的仅供后面备考的同学参考题量的比例。有一点要留意这批笔试的选择题里出现了好几道“下列哪种排序算法在平均情况下时间复杂度为O(n log n)”这样的基础题也有几道“对于Java HashMap在JDK 1.8之后当链表长度超过8时会转换成红黑树”这类细节题说明基础掌握扎实比押题更管用。2. 编程题全解析业务场景包装下的综合算法题2.1 原题大意与思路拆解笔试的编程题通常是一道完整可运行的算法题不只是一句简单的LeetCode原题。我抽到的题目大意是这样的给定一个由多个酒店组成的列表每个酒店有入住时间、离店时间和每晚价格三个字段。现在需要你实现一个函数找出在用户给定的连续入住日期段内能够提供“连续住宿且总价最低”的酒店组合返回对应酒店ID和总价。注意一个酒店的连续住宿区间不能重叠且用户指定的整个日期段必须被完整覆盖不能存在某一天没有酒店入住。这道题的核心实际上是“带权区间覆盖最小成本”问题说白了就是动态规划。你可以把它理解为在一条时间数轴上给你若干个区间酒店入住时间到离店时间每个区间有一个权重总价格求覆盖指定完整范围的区间组合使得总权重最小。看到这道题第一反应是贪心但很快就能发现贪心是错的。因为区间价格并非按天数均匀分布一个覆盖10天的酒店可能总价比“两个覆盖5天的酒店”更贵也可能更便宜必须尝试所有可能的分割点。标准解法就是动态规划定义 dp[i] 表示覆盖到第 i 天从用户入住日期的第一天开始数i从0到总天数所需的最低总价。初始化 dp[0] 0dp[i] 正无穷表示不可达。然后遍历每个酒店如果该酒店的入住时间正好等于或早于当前覆盖到的日期段起点且离店时间晚于当前覆盖位置就可以尝试用它来从上一个状态转移过来。具体转移方程对于每一天 i如果存在一个酒店区间 [l, r) 使得 l i覆盖终点正好接上那么 dp[j] min(dp[j], dp[i] price)其中 j r表示从第 i 天到第 r 天这段被这个酒店覆盖了。如果一个区间从 l i 开始那其实它在之前已经被考虑过这里为了方便处理一般会把所有区间按开始日期排序然后从小到大枚举或者直接按天数把合法区间都存下来。这里不能只用一个dp数组简单遍历因为区间可能覆盖多天直接用贪心选最便宜的单天价格是完全错误的。必须把“日期段连续”这个约束显式建模确保每个酒店的覆盖区间首尾相接。我当时写的核心代码Python版本是这样的def min_total_price(hotels, start_day, end_day): # hotels: list of tuples (hotel_id, start, end, price_per_night) # start_day, end_day: int, 表示用户入住开始日期和离店日期以天数为单位 n end_day - start_day 1 # 总天数 INF float(inf) dp [INF] * (n 1) dp[0] 0 # 将每个酒店转换为从start_day相对的第几天到第几天 intervals [] for hid, s, e, price_per_night in hotels: if s end_day or e start_day: continue l max(s, start_day) - start_day r min(e, end_day) - start_day total_price price_per_night * (e - s) # 注意总价是每晚价格乘以原始住宿天数如果截断了则按实际覆盖天数计算 # 但如果酒店提供的区间是原始完整的实际上价格通常按整段算不过按每天价格乘以覆盖天数即可 total_price price_per_night * (r - l) intervals.append((l, r, total_price)) # 按开始日排序也可以用其他方式 intervals.sort(keylambda x: x[0]) for i in range(n): if dp[i] INF: continue for l, r, tp in intervals: if l i and r i: if dp[r] dp[i] tp: dp[r] dp[i] tp elif l i r: # 如果区间从更早开始且已经覆盖到了第i天之后也可以直接扩展 # 但是为了避免重复计算这里需要更精细的状态定义 pass # 上面注释部分留了坑我们需要重新设计 return dp[n] if dp[n] ! INF else -1这里我踩了个坑如果单纯按 l i 来判断会漏掉那些“开始日期在起点之前、但覆盖到了当前第 i 天”的酒店。比如一个酒店从用户开始日期前一日入住一直住到用户日期段的第三天那么它显然能覆盖用户整个第一天但它并不满足 l i它的 l 是0而i是0时倒满足如果从i1开始它的l是0不等于1。所以更稳定的做法是把每个酒店区间视为我们可以从当前覆盖位置的某一天开始使用只需要保证 hotel.start 当前已覆盖天数并且 hotel.end 当前已覆盖天数。这时它的“覆盖长度”是 hotel.end - current_day。所以可以按已覆盖天数从小到大遍历在每一步尝试所有可选酒店。更清晰的动态规划写法是def min_price_cover(hotels, start_day, end_day): n end_day - start_day dp [float(inf)] * (n 1) dp[0] 0 for i in range(n): if dp[i] float(inf): continue for hid, hs, he, price_per_night in hotels: if hs start_day i: continue # 酒店开始日期必须不晚于当前需要覆盖的日期否则不能从这个日期开始 if he start_day i: continue # 酒店在需要覆盖之前就离店了无法衔接 j min(he, end_day) - start_day # 这个酒店可以覆盖到的相对结束日期 if j i: dp[j] min(dp[j], dp[i] price_per_night * (j - i)) return -1 if dp[n] float(inf) else dp[n]这个写法把“酒店开始日期不晚于当前待覆盖日”作为判断条件并把覆盖长度按实际使用的天数计算逻辑比较简洁也不需要排序。实际笔试时我花了20分钟才把转移方程想清楚因为一开始总想着按区间排序然后做线段树优化后来发现数据范围是 n 1000酒店数量 100直接 O(n * m) 复杂度足够了完全没必要搞复杂化。笔试时的数据范围很友好基本就是给暴力动态规划用的。如果需要处理大量数据就得考虑使用堆优化的Dijkstra思想或者DP 线段树优化但携程这种笔试一般不会把数据范围设得特别变态先把基础DP写对就好。2.2 代码实现与输入输出细节牛客网笔试通常需要自己处理标准输入输出所以必须熟练掌握自己所选语言的输入输出模板别在这种地方浪费时间。我用的输入格式大概是第一行是三个整数酒店数量 m用户开始日期 s用户结束日期 e。 接下来 m 行每行有四个整数酒店ID入住日期 h_s离店日期 h_e每晚价格 p。比如3 1 10 101 1 4 200 102 4 10 150 103 1 10 400这段输入表示有3个酒店用户需要覆盖第1天到第10天。酒店101覆盖第1天到第4天每晚200元酒店102覆盖第4天到第10天每晚150元酒店103覆盖第1天到第10天每晚400元。那么最优方案可以是101102总价2003 1506 1500小于103的400*93600所以返回101、102和1500。实际输出要求可能是第一行输出总价第二行输出选择的酒店ID列表以空格分隔。也可能要求按某种格式返回具体看题目。我当时写代码时多用Python因为写DP快但输出格式要特别注意有些题要求ID从小到大排序有些要求按入住顺序排序需要仔细读题。我当时就差点把ID顺序搞反。我也写了一份C版本用于对比其实C写这类题更快但要处理内存分配和字符串分割如果不熟练反而容易翻车。选自己最熟的语言就好毕竟笔试的核心是算法思路不是语言炫技。2.3 笔试中算法的常见变体与应对携程的算法题虽然每次不一样但出题风格通常都是“业务场景 经典算法”。比如另一批同学遇到的可能是“机票订单合并”“景点路线规划”“最优优惠券组合”本质都是区间DP、背包、图的最短路等。所以备考时重点刷这几类题即可区间调度 / 区间覆盖问题常用来包装成酒店、会议室、课程安排等业务。核心是排序后贪心或动态规划。背包问题0-1背包、完全背包容易包装成优惠券、预算分配、短途游路线组合。图的最短路径Dijkstra、Floyd常用来包装成航班换乘、景点间最短路。拓扑排序可能出现在任务依赖、订单处理顺序等场景。哪怕没刷过原题也要熟悉这些算法模板考试时“翻译”成业务题即可。我有个朋友笔试时遇到了“多个视频流同时播放求不重叠的最大观看总时长”其实就是经典的最大不相交区间数贪心直接解决。携程很多题并不会把题目包装得太绕只要你识别出核心模型代码是水到渠成的事。3. 选择题考点梳理基础功底决定成败3.1 计算机网络重点在TCP和HTTP选择题里网络部分的比重很大我印象最深的是HTTP相关的几道题可能是因为携程本身就是在线旅游平台对HTTP协议格外关注。考到的点包括HTTP状态码403 Forbidden、404 Not Found、500 Internal Server Error、502 Bad Gateway的含义以及200、301、302的区别。注意301和302的区别永久重定向 vs 临时重定向题目会给具体场景让你判断。TCP三次握手与四次挥手SYN、ACK、FIN字段的使用以及TIME_WAIT出现的原因。有题问到为什么TIME_WAIT要等待2MSL答案是为了保证最后一个ACK能到达对端防止旧连接中的重复报文干扰新连接。HTTP与HTTPS的差异HTTPS在HTTP和TCP之间加了TLS/SSL层默认端口443证书的作用是身份验证和加密传输。Cookie与Session的区别Cookie存客户端Session存服务端Session依赖Cookie传递SessionID。备考网络部分建议把TCP/IP协议栈、HTTP状态码、HTTPS握手过程、DNS解析流程过一遍即可。这些属于计算机基础中的基础笔试出现概率极高而且变化不多。3.2 操作系统进程、线程与内存操作系统选择题主要考察进程与线程的区别、进程状态转换、死锁四大条件、内存分页与分段以及常见的调度算法。我这次遇到的一道题是这样的多个线程同时访问一个共享变量不加锁可能导致哪些问题选项包括死锁、数据不一致、栈溢出、程序崩溃。正确答案是数据不一致和程序崩溃但要注意“死锁”不会因为不加锁而产生这属于概念混淆题。后来我想明白这题考察的是“竞态条件”及其危害。还有一道题是关于进程状态的运行、就绪、阻塞三个状态之间的转换以及哪些转换是不可能的。比如“阻塞 - 运行”就是不可能的因为阻塞的进程必须先变成就绪再由调度器选择运行。这种题很基础但做错的人很多。内存分页部分的题目相对简单给了页大小4KB逻辑地址32位问页内偏移占多少位。答案12位。只要你掌握页内偏移位数 log2(页大小)基本不会错。操作系统备考不用看太深重点看进程线程模型、死锁、调度、内存分页、虚拟内存这几个章节。深入理解PV操作和读者写者问题对笔试帮助不大因为在选择题里顶多考一个概念。3.3 数据库重点在索引与SQL优化数据库选择题涉及SQL语句、索引原理、事务隔离级别、范式等。我记得有一道题是关于B树索引的为什么InnoDB选择B树而不是B树或红黑树答案要点就是B树非叶子节点不存储数据相同磁盘页可以容纳更多索引项树高度更低同时叶子节点通过指针相连范围查询效率高而红黑树高度高、数据量大时IO次数多。这道题在多个互联网公司笔试中都出现过可以当作必背题。SQL相关的选择题则考到了LEFT JOIN与INNER JOIN的结果差异还考了GROUP BY HAVING的用法。基础的SQL语法必须熟练尤其是多表联查、子查询、聚合函数、索引命中规则最左前缀匹配这些。事务隔离级别也有考到重点区分读未提交、读已提交、可重复读、串行化这四种隔离级别分别解决什么问题。携程这类互联网公司通常用MySQL默认的RR级别所以“可重复读”能避免不可重复读但仍然存在幻读的可能在MVCC下可部分解决。这题有一定深度建议专门理解一下。3.4 语言特性Java和C都有涉及技术通用岗的考生有Java为主、也有C为主、Python为主的所以语言题一般是多选题让你选出正确描述。题目本身不偏向某一种语言而是考察基本语法和原理。Java部分高频考点包括HashMap的底层结构数组 链表/红黑树加载因子0.75链表转红黑树的阈值是8红黑树退化链表的阈值是6。ArrayList与LinkedList的区别ArrayList基于动态数组随机访问O(1)LinkedList基于双向链表插入删除O(1)但要先找到位置随机访问O(n)。线程池的核心参数corePoolSize、maximumPoolSize、keepAliveTime、BlockingQueue以及拒绝策略。自动拆装箱Integer的缓存范围默认-128到127在这个范围内直接用比较是true超出则为false。这是经典的智商题。C部分高频考点new/delete与malloc/free的区别前者是运算符自动调用构造函数和析构函数后者是库函数只分配/释放内存。虚函数、纯虚函数、虚函数表、动态多态的机制。vector扩容机制每次扩容通常是1.5倍或2倍会导致迭代器失效。const的各种用法顶层const与底层constconst成员函数。如果你用Python也要了解Python的GIL、可变对象与不可变对象、列表与元组的区别还有深拷贝与浅拷贝。不过这些在携程的笔试中比较少出现可能是岗位偏好Java/C的缘故。3.5 分布式和Linux携程的亮点指标携程笔试里出现了一些分布式和Linux的基础题这和它业务规模大、技术栈偏Java/中间件的背景有关。我记得有两道题印象比较深一道多选题问哪些方案可以用于分布式系统的会话保持选项有Nginx IP Hash、Redis集中式存储、Cookie携带SessionID、数据库存储Session。这四个其实都可行但需要根据场景取舍。如果不敢确定多选就少选比如确定Redis和Cookie是常用的数据库存储虽然有但性能不佳不应选。这道题很可能有陷阱最终我还是只选了前两个拿了部分分。当然如果是不定项选择少选可能不得分具体还是看题目说明。另一道题问Linux系统中查看端口占用情况的命令是什么答案包括netstat -anp、ss -lntp、lsof -i:port。这个属于运维基础技术岗必须掌握。还有一道是查找文件中含有“error”的行并统计行数正确的管道命令是grep error xxx.log | wc -l挺简单的。Linux常用的命令建议都过一遍包括文件操作、权限、进程管理、端口网络、日志分析。刷题之外多在实际环境敲一敲比死记硬背强得多。4. 情景题与逻辑推理题考察解决问题的思路4.1 排序算法与复杂度的综合应用情景题部分并不是简单的智力题而是给出一个业务场景让你选择最合适的算法或方案。比如有一道题某个日志系统需要将海量订单数据按照时间戳排序数据量超过内存应该如何设计排序方案选项包括快速排序全量内存排序、归并排序内存 外存、位图排序、桶排序。正确答案显然是外归并排序。题目出得很实际因为携程的订单日志、用户日志都会有海量数据的排序需求。这种题考的不仅仅是排序还考了你对数据量级和存储约束的理解。还有一道题问要求在O(n log n)时间和O(1)额外空间内对链表排序适合用什么排序算法答案是归并排序。因为链表不能随机访问快排复杂度退化到O(n^2)堆排序实现复杂且需要O(1)空间支持而链表的归并排序可以做到时间O(n log n)、空间O(log n)递归栈或者O(1)自底向上通常笔试里认为O(1)或O(log n)均可接受。我备考时把常见的排序算法冒泡、选择、插入、快排、归并、堆排的时间复杂度和稳定性都整理成了一张表考前背一遍发现笔试中直接或间接考的至少有3题所以强烈建议你也整理一下排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定另外还有一个容易被忽略的点在“大量数据无法一次装入内存”的场景下外排序写磁盘的次数和归并路数有关最佳归并树霍夫曼树可以减少IO。虽然笔试未必深入到这一步但如果能在论述题中提出来会比较亮眼。4.2 日志与异常排查贴近实际工作流有一道情景题是这样的假设线上系统某接口的P99延迟突然从100ms升高到2000ms你怎么排查选项有查看CPU/内存监控、查看慢SQL日志、查看GC日志、查看Redis缓存命中率、回滚最近发布的代码。这些选项全都合理但需要排优先级。我当时选了查看监控、慢SQL、GC日志、最近发布记录优先级不确定的情况下就先把通用的手段都选了。不过这种题很可能需要多选只要不是互斥选项尽量全选也是策略。实际上这道题背后考察的是“线上故障排查流程”先看监控指标确定瓶颈方向再结合日志和发布记录缩小范围。不像纯理论题那么死板但要求你有工程经验。对于还没工作的在校生建议多了解一下常见的线上问题排查思路比如CPU飙高、内存溢出、接口超时、数据库慢查询、缓存穿透等这些在面试和笔试里都非常常见。另一道日志题是有100GB的访问日志需要统计URL访问次数Top100设计一个方案。这道题本质是“超大文件求TopK”标准解法是分治将大文件哈希分成多个小文件每个小文件用HashMap统计URL频率分别得到每个小文件的Top100最后再对所有Top100进行归并。笔试给的是选择题你选“按URL哈希分桶 每个桶内使用HashMap 堆排序”就行。这类题目不难关键是要把“MapReduce”思想说清楚分而治之归并汇总。4.3 逻辑推理题与概率题智力题部分不多但有一道概率题让我想了很久一个袋子中有5个红球和3个蓝球不放回抽取并记录颜色连续抽到两个红球的概率是多少一开始我差点直接算成 (5/8)*(4/7)后来发现题目的描述可能是“已经抽了若干次后的下一次”需要关注条件概率。还有一道题前100个自然数中数字9出现的次数是多少我算出来是20次9、19、…、99共10个其中90-99的十位9有10个但要注意99里有两个9所以实际是20次如果数字只算9一次的话则是10次。这种题其实很考验细心程度一定要看清楚是“9这个数字出现多少次”还是“包含9的数有多少个”。逻辑推理我遇到的是甲、乙、丙、丁四人中一人是程序员已知说法只有一句为真问谁是程序员。这种题老实列表推导别靠直觉。一般先把每个人的猜测列出来找矛盾项。我花了五分钟最后还是推出来了虽然耗时但正确率能保证。这类题目备考时多刷一点公务员行测的逻辑判断题就行不用太紧张。笔试中智力题占比低就算全错也不会影响大局但能做对还是尽量做对。5. 笔试实操经验时间分配与答题策略5.1 我自己的做题顺序和节奏整场笔试120分钟我设定的策略是先花3分钟快速浏览所有题目对类型和难度心里有数然后直接做编程题因为编程题分值最高且最需要思考和调试放最后容易因时间不足而草草交卷。编程题我大概用了35分钟包括思考、编写、测试。接下来做单选和多选这部分总共用了40分钟。选择题看起来很简答但很多干扰项就是概念模糊的陷阱所以宁可读题慢一点也别掉坑。我给自己定的规则是遇到不确定的多选题只选完全有把握的选项少选不得分也比错选扣分强——但这里需要先确认是否倒扣分如果明确“错选倒扣分”就保守选如果没有倒扣分不确定的也尽量选上争取得分。最后做情景题和逻辑题用剩余的时间慢慢分析。情景题本质上也是考察思维链时间充裕的话性价比很高。综合来说我在交卷前留了5分钟检查主要检查编程题的输出格式、变量命名、边界情况比如入住日期和离店日期的开闭区间并确保每一道选择题都填了答案。千万不要空题特别是单选题蒙一个也有概率得分。5.2 编程题的边界条件处理编程题考察的不仅仅是核心算法还特别关注边界条件。我这次在写DP时遇到的一个问题是如果酒店入住日期晚于用户开始日期但离店日期正在用户开始和结束之间那么用户开始日期到酒店入住日期之间就没人住这显然不合法必须把这种情况屏蔽。对于这一点我的转移方程中只有 hs 当前的 start_day i 才允许使用酒店实际上就保证了从用户日期段第一天起不存在空窗期。另一个边界是价格计算。题目中“每晚价格”乘以“实际住宿天数”才是总价但天数的计算要明确如果入住1号、离店4号是住了3晚1、2、3号晚上还是4晚一般业务里“离店日期”就是退房当天所以实际天数是离店日期减入住日期。我的输入样例写的是1到4那么算3晚。笔试中一定仔细阅读题目给出的示例与计算方式有时他们会用“入住时间戳”不是整数天数还要求按小时算这就更复杂了。还有输出时的酒店ID顺序。如果题目要求“按入住先后顺序输出”你需要根据酒店原始入住时间排序后再输出如果要求“按酒店ID升序”则需在得到组合后排序。我保存DP路径时默认按选择顺序记录下来如果题目要求ID升序就再排一下。这种小细节往往决定能否AC宁可多花一分钟确认格式也不要因为格式错误丢失大量分数。因为DP只记录最低价格如果要输出具体选择的酒店ID需要额外维护一个 path 数组或 prev 状态。我在实际书写时在dp之外增加了一个pre列表每次状态转移时记录当前新的覆盖结束日对应的是哪个酒店和上一个状态下标最后倒推得到路径。这个操作不难但容易写错测试时要手动构造几个案例验证。下面是我笔试后整理的一个更完整的Python示例包含路径回溯def solve(): import sys input_data sys.stdin.read().strip().split() if not input_data: return it iter(input_data) m int(next(it)) start_day int(next(it)) end_day int(next(it)) hotels [] for _ in range(m): hid int(next(it)) hs int(next(it)) he int(next(it)) p int(next(it)) hotels.append((hid, hs, he, p)) n end_day - start_day INF float(inf) dp [INF] * (n 1) pre [-1] * (n 1) # 上一个状态下标 use_hotel [-1] * (n 1) # 转移使用的酒店ID dp[0] 0 for i in range(n): if dp[i] INF: continue current start_day i for hid, hs, he, p in hotels: if he current: continue start_pos max(hs, current) end_pos min(he, end_day) if start_pos end_pos: continue j end_pos - start_day if j i: continue cost p * (end_pos - start_pos) if dp[j] dp[i] cost: dp[j] dp[i] cost pre[j] i use_hotel[j] hid if dp[n] INF: print(NO_SOLUTION) else: print(dp[n]) # 回溯路径 path [] cur n while cur 0 and use_hotel[cur] ! -1: path.append(use_hotel[cur]) cur pre[cur] # 这里得到的是逆序需要反转并按酒店实际开始时间排序输出 path.reverse() # 如果要求按ID升序则 sorted(path) print( .join(str(x) for x in sorted(path)))注意这里我的循环中对于每个当前覆盖日 i会尝试所有酒店如果酒店开始时间早于当前日也没问题因为 cost 只计算从当前日到其离店日的差值。这个写法可以正确处理多种情况但要注意酒店覆盖区间如果跨越当前日它那部分多出来的之前天数不需要再付一次钱其实这里隐含假设酒店的价格是按每晚单价乘以实际住宿天数如果跨越覆盖那么从当前日起到离店日只需支付这些天的费用之前天数已经包含在dp[i]里了。如果酒店区间从更早开始则之前那几天的费用已经计算在dp[i]中这个转移没有问题。但逻辑上 dp[i] 可能来自某个酒店或者其他酒店如果当前酒店从更早开始那 dp[i] 应该是包括了该酒店前面天数费用的状态这里其实存在逻辑漏洞比如 dp[i] 可能是从另一家酒店转移来的这时再用这家从更早开始的酒店会把同一时间段重复计费。因此更稳妥的转移是只考虑 hotels 的入住时间等于当前待覆盖日期的那些酒店或者将DP状态设计为“以已选择的最右端点为状态”保证每个酒店的开始日期就是当前覆盖位置的日期。但也可以采用“将酒店按开始时间排序逐个考虑”的区间DP避免重叠区间重复。在实践中为了简便且避免重叠问题我建议采用“按结束日遍历”的思路把所有酒店按离店时间排序维护一个best数组记录覆盖到每个位置的最低价格然后使用类似于“带约束的单源最短路”进行转移但这里不再展开。笔试时数据小用暴力DFS剪枝可能都能通过不过现场还是选择了最不容易出错的“从当前天开始、使用开始日不晚于当前天的酒店但只允许覆盖未覆盖的连续区间且覆盖区间不重叠”的写法这种写法容易有漏洞建议自己构造几个用例测试。比如下面这个用例2 1 5 101 1 5 100 102 2 4 10用户覆盖第1到第5天。正确的方案其实是唯一的只能选101因为102不覆盖第1天。但我的上述写法在i0时101的start_pos1end_pos5j5所以dp[5]500。这没问题。但如果存在101覆盖1-4和102覆盖2-5那只有一个合法方案是101但是我的写法在i0时先使用101转到j34-13之后i1怎么办一旦i0转移到了j3后续i会跳到实际上循环是每次i从小到大i1时会再次尝试使用101但由于dp[1]此时可能还是无穷大因为dp[0]只能转移到j3而dp[1]没有被填充那么对于cover[1]这一段空窗101从第1天开始覆盖但转移直接跳到第4天结束其实i1、i2在dp中仍然是INF但转移已经直接到j3不需要逐天填充。这没问题。如果存在一个酒店从第2天开始在i1时可以选择但我们必须先有dp[1]的状态。dp[1]如何被填充可以通过另一个覆盖第1天到第2天的酒店或者酒店101覆盖1-2天。如果当前是从i0直接跳到j3则dp[1]没被填充那么后续j3之前的一天即第2天就已经被酒店101覆盖了不对j3表示覆盖到第4天之前这里定义有歧义。我的代码中用 start_pos 和 end_pos 计算j 是 end_pos - start_day是相对结束日。比如s1, e5酒店101覆盖1-4则end_pos 4, j 3表示dp[0]转移到dp[3]表示覆盖了相对的第1,2,3天绝对1,2,3日这是不对的覆盖到第4天之前的3天但实际上从1号到4号是3晚覆盖了1号、2号、3号夜晚到4号白天退房所以绝对覆盖了第1、2、3号也就是相对的1天,2天,3天下标0,1,2dp[3]表示覆盖了3天没错。所以如果要衔接2号入住的酒店需要dp[1]或dp[2]状态实际上如果1号已经住了1晚2号可以换酒店。但酒店101从1号到4号是可住的如果你中途换了酒店那么101酒店剩余2晚就不能再使用了这是允许的。我的转移直接跳到j3表示连续住了101的3晚并不是必须拆分。但从dp[3]之后下一个需要覆盖的日期是绝对4号下标3。此时选中102从2号到5号由于102开始日期2号早于当前4号我的代码会允许使用但这里就会重复计费因为102覆盖的2号到4号已经被101覆盖了。因此我刚才说的写法不允许重叠但没限制“酒店开始时间必须等于当前待覆盖日期”这就会出现错误。所以最稳妥的转移条件是要求酒店的入住开始时间等于当前待覆盖日期即 hs start_day i。因为对于完整覆盖整个区间每个酒店使用的开始日期必须正好是前一个酒店覆盖结束的那一天否则要么有空窗要么有重叠。所以正确条件就是 l i。但这会漏掉开始日早于当前覆盖日但未使用过的酒店不过在连续性约束下这种酒店要么在初始阶段就用了它覆盖整个区间要么不能作为后续衔接。因此我们只需要考虑“开始日恰好等于当前待覆盖日”的酒店并把其总价计算为全程价格而非部分天数这样就不会漏解。那么我上面的错误写法应该修正为for i in range(n): if dp[i] INF: continue current start_day i for hid, hs, he, p in hotels: if hs ! current: continue j he - start_day if j i: dp[j] min(dp[j], dp[i] p * (he - hs))这样每个酒店的覆盖区间就是完整的且必须与当前覆盖位置无缝衔接。由于酒店入住时间hs可能等于当前待覆盖日离店时间he就是结束日那么实际覆盖天数是he-hs转移后j he - start_day。这个写法完全正确并且不需要考虑重叠。但如果酒店区间一开始就在用户起始日之前比如hs start_day那么它无法被使用因为用户起始日当天已经开始不能让该酒店覆盖起始日之前的空档但若酒店从用户起始日前一天开始住到用户第二天它确实覆盖了用户起始日是否合法在实际业务中是合法的因为用户可能在前一天晚上入住一直住到第二天。这种酒店在开始日早于用户起始日但结束日大于起始日它是覆盖了用户起始日的应该被允许。在这种情况下“hs current”条件会漏掉它。所以更一般的正确做法是对于每个酒店如果 hs current 且 he current则它可以作为从当前日开始的住宿选择但用户只需支付从 current 到 min(he, end_day) 天数的费用之前 hs 到 current 的天数费用已经支付过假设这个酒店是当前已经入住的酒店。但由于我们无法在状态中记录当前正在住的酒店所以处理起来更复杂。最简化且不易出错的方法是将酒店区间视为“可拆分”的选择从用户起始日开始每一天都可以选择任意一个覆盖该天的酒店入住且可以在任意连续天数后自动退房。但这本质上就是“区间覆盖的动态规划”只是转移时要考虑酒店的开始日期必须不晚于当前日且当前日必须在酒店区间内同时因为不确定酒店从哪天开始入住我们令支付天数从当前日开始算这是不准确的。为了避免笔试时纠结我建议使用最常规的区间DP先将所有酒店区间按起点排序dp[i]表示覆盖到第i天绝对日期的最小费用然后遍历所有酒店如果该酒店的开始日期等于或早于状态i且结束日期大于i则可以用它从i覆盖到它的结束日期支付价格为总价或按实际覆盖天数计算。为了保证不重叠需要保证该酒店的开始日期等于i或者该酒店开始日期之前的区间已经cover且该酒店开始日期在i之前这会导致重叠。因此严格解法是状态i表示“当前连续覆盖区间的最右端”我们只考虑起点正好等于i的酒店。对于起点早于i的酒店要么它已经包含在之前的覆盖中要么不能在i处开始否则就会重叠。所以常规解法就是只允许起点等于当前覆盖到位的酒店。如果存在“住到第二天再换酒店”的场景其实等价于有两个酒店前一个酒店结束日期正好是后一个酒店开始日期所以后一个酒店的起点等于前一个的结束日。因此“起点等于当前覆盖日”并没有漏掉合法解。对于酒店开始日早于用户起始日的情况由于起点小于起始日我们不能在起始日用它的“起点”来转移但我们可以构造一个虚拟酒店其开始日为起始日结束日为该酒店离店日价格按从起始日到离店日计算。所以将所有酒店区间裁剪到用户日期段内并把开始日裁剪到当天即可。具体就是对每个酒店取其有效区间为 [max(hs, start_day), min(he, end_day)]然后我们基于这些裁剪后的区间做起点等于当前覆盖日的转移并支付按裁剪后的天数计算的价格。这样就能够处理开始日早于起始日的情况。因此正确的DP是将每个酒店裁剪为 [L, R]其中 L max(hs, start_day)R min(he, end_day)如果 L R 则丢弃。总费用 p * (R - L)动态规划状态 i 表示从 start_day 起覆盖到当前日期包括当前日期作为夜晚开始日我们用天数索引dp[t] 表示覆盖了从start_day开始的 t 天t current - start_day。则当 t 总天数时遍历所有酒店如果 L - start_day t则可以转移 dp[R - start_day] min(dp[R - start_day], dp[t] p * (R - L))。这样就能正确处理所有合法区间且不会重叠。这个写法的条件是酒店裁剪后的开始日期必须等于当前覆盖天数 t 对应的日期。若酒店开始日期早于但结束日期晚于当前裁剪后开始日期便是当前日期所以可以转移。因为在裁剪时 Lmax(hs, current_date)但在前面预处理时 current_date 未知所以我们可以不对每个酒店裁剪到 current_date而是只针对酒店判断 hs current_date he然后把覆盖长度从 current_date 到 he。但这会与重叠问题冲突。更精细的方式是允许一个酒店从中间开始使用但支付价格按当前日到离店日计算不过这种情况在实际中表示用户在该酒店入住当晚之后某天换酒店原酒店中间剩余天数未使用是允许的支付按实际住宿天数也是合理的。但是这种操作会导致可能从状态i衔接一家酒店而其开始日期早于i这在时间线上看起来是从酒店住宿中途退出再住回去实际不可能因为如果用户已经在该酒店住了几天那么这几天的费用已经包含在之前的状态里从状态i开始继续住这家酒店也是合理的但不是新的酒店选择。所以这种“同一酒店分段付款”可以通过把酒店按起点转移来实现不需要在中间状态继续转移同一酒店。但为了支持用户在某天换酒店我们只允许从状态i转移到下一家酒店要求下一家酒店的开始日期正好是i裁剪后而不是允许任何覆盖i的酒店。因为如果一家酒店从早于i开始那么用户一直没有换酒店它的开始日期必然是当前连续覆盖起始点而不是中间某天。所以起点必须等于i。这样我们无需考虑酒店结束日期大于i但开始早于i的情况。因为若开始早于i说明用户在该酒店已入住多日那么在它开始的那天就已经转移了不需要再在中间转移。所以核心就是每个酒店只允许从其入住日开始使用不能从中间插入。所以最终推荐的DP是预处理裁剪区间然后按起点匹配转移代码如下def solve(): import sys data sys.stdin.read().strip().split() if not data: return it iter(data) m int(next(it)) start_day int(next(it)) end_day int(next(it)) hotels [] for _ in range(m): hid int(next(it)) hs int(next(it)) he int(next(it)) p int(next(it)) L max(hs, start_day) R min(he, end_day) if L R: continue hotels.append((hid, L, R, p * (R - L))) n end_day - start_day INF float(inf) dp [INF] * (n 1) pre [-1] * (n 1) use [-1] * (n 1) dp[0] 0 for t in range(n): if dp[t] INF: continue cur_date start_day t for hid, L, R, cost in hotels: if L cur_date and R cur_date: nt R - start_day if dp[nt] dp[t] cost: dp[nt] dp[t] cost pre[nt] t use[nt] hid if dp[n] INF: print(NO_SOLUTION) else: print(dp[n]) path [] cur n while cur 0: path.append(use[cur]) cur pre[cur] path.reverse() print( .join(str(x) for x in path))这个代码简洁且正确。我笔试时写的版本更复杂因为当时没想清楚幸好时间充裕测了几组用例修正过来。这里提醒大家动笔前一定先想清楚状态定义和转移条件尤其是区间问题很容易出现重复计费或漏解。5.3 面对不会的选择题怎么蒙才不亏选择题不会做的时候蒙也要有策略。先看选项是单选还是多选。多选题目如果说明“漏选得部分分错选不得分”那不确定的选项坚决不选确保拿到确定的分如果没有漏选得分的说法那只要不确定的选项至少有一半概率是对的可以尝试全选因为多选不会倒扣分的话碰运气也不亏。对于单选题先排除明显错误的选项。比如问了TCP的端口号不可能选80以外的等等。如果两个选项描述一个概念的两种相反情况那正确答案大概率是其中一个可以结合常识判断。如果有计算题先粗略估算数量级再选最接近的答案不要精确计算浪费时间。我记得有一道数据库题问“事务隔离级别从低到高排序正确的是”。选项有四个读未提交 读已提交 可重复读 串行化。这个只要背过就能选对。如果没背过可以根据“读写限制越强越安全”的顺序推也能推出来。还有很多类似的排序题比如进程调度算法、TCP状态等核心是平时积累。我笔试时遇到的智力题有一道不确定是关于“三个盒子分别装红红、白白、红白标签全贴错从一个盒子摸一个球推断所有盒子”。这题很经典但我在现场一时紧张还是想清楚了标签全错所以摸标有“红白”的盒子如果摸出红球说明该盒是红红剩余两盒为白白和红白如果摸出白球说明该盒是白白剩余两盒为红红和红白。这样就明确了。这种题属于“行测逻辑”多刷几道就不怕了。5.4 时间不够时先守住编程题再保单选如果大家做题碰到时间只剩15分钟但编程题还没写我强烈建议放弃后面的选择优先把编程题框架写出来至少能通过部分测试用例。因为编程题分值高而且有部分正确率只要思路对、能跑通基础案例就能拿不少分。选择题倒扣分设置下乱蒙可能一分不得。我笔试时编程题花了35分钟做完后还剩85分钟相对充裕如果编程题卡壳可以先用5分钟写下伪代码拿框架分再转去做选择题最后再回头补全。但千万别在选择题上耗太久导致编程题没时间。牛客网笔试平台的编程题通常是按通过用例的百分比给分所以即使不能AC也要尽量把核心逻辑写出来极端情况返回合理值能够通过部分简单用例。比如我上述DP题如果写不出完整回溯至少输出dp[n]的数值就能拿分因为很多测试用例可能只需要总价不一定需要酒店ID。6. 不同语言环境下的笔试答题建议6.1 Java考生注意输入模板和集合类的快速使用Java笔试答题时我见过同学因为Scanner读取超时导致超时尤其是数据量一大Scanner效率确实低。建议使用BufferedReader InputStreamReader StringTokenizer模板大致如下import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int m Integer.parseInt(st.nextToken()); int s Integer.parseInt(st.nextToken()); int e Integer.parseInt(st.nextToken()); // ... } }另外使用HashMap、PriorityQueue时要注意泛型。Java的PriorityQueue默认是小顶堆如果想要大顶堆需要重写Comparator或者把元素取负数。笔试时很容易在这里犯错。排序时数组和List的Comparator写法也要熟悉比如按区间左端点升序Arrays.sort(intervals, (a, b) - a.start - b.start);Java的不定长数组声明可能有些麻烦建议使用ArrayList避免一次性分配过多内存。6.2 C考生STL和边界条件都要注意C读入比较简单cin 就可以但如果数据量大关闭同步会更快ios::sync_with_stdio(false); cin.tie(nullptr);这个技巧很多人会忽略。使用vector、map、set等STL时注意迭代器失效问题比如在遍历时删除元素要特别小心。C的std::sort默认升序可利用lambda自定义排序。std::priority_queue是大顶堆小顶堆需要greaterint。DP数组用vectorlong long避免溢出注意int可能不够。6.3 Python考生能快速写但要注意超时Python写代码快但运行速度慢。笔试平台一般会放宽Python的时间限制但遇到O(n^2)且n1e5的题目还是会超时。如果发现复杂度太高可以通过PyPy来提高执行速度牛客支持提交语言选择PyPy3并且尽量少用递归用迭代。输入使用sys.stdin.read()一次性读取避免input()逐行读取的耗时。7. 笔试常见问题与避坑指南7.1 忘记看清输入范围和边界很多同学卡在边界条件上。比如酒店入住时间可以是0也可以是很大的值用户开始和结束日期可能包含矛盾开始大于结束多个酒店ID可能重复每晚价格可能为0。笔试时最好在代码中加一层防御处理如果end_day start_day直接输出0或空方案。价格是整数但DP初始值用大数比如10**18避免整型溢出。7.2 没有本地测试导致答案错误笔试系统中虽然自带示例输入输出但往往只有一个示例。我建议在本地IDE里至少手写3个自定义用例来验证。比如上述DP题分别测试只有一个酒店完全覆盖输出其总价。多个酒店可拼接但中间有空窗输出NO_SOLUTION。多个酒店可拼接且有重叠验证不会重复计费。酒店开始日期早于用户开始日期验证裁剪后正确。用户开始和结束相同天即不需要住宿输出0。如果没有这些测试很容易因为细节错误丢分。7.3 系统切屏误判牛客系统会记录切屏次数有些同学只是不小心点了浏览器弹窗就被警告。建议大家考前关闭所有无关浏览器标签页和聊天软件把IDE窗口调到最大避免鼠标误滑出系统区域。如果真误触一次不用慌只要不是严重频繁一般系统只是警告不会立即取消成绩。但绝不能尝试搜索答案切屏检测加上摄像头一旦判定作弊整个招聘流程都会受影响。7.4 多选不确定时少选还是多选由于没有统一的笔试说明每次的规则都可能变化。我这次明确看到“错选不得分漏选得部分分”的提示所以策略就很简单只选有把握的选项不确定不选。如果题目没有这个提示而是“多选题目全部选对得满分选对但不全得部分分有错选得0分”也可以保守处理。但如果是“多选选错倒扣分”那更不要冒险。总之答题前先读清楚题目说明不要凭惯性。7.5 智力题耽误过多时间智力题通常只有一两道一道题卡住5分钟以上就先跳到后面避免因小失大。整个笔试120分钟编程题加选择已经占了大部分智力题如果耗时太多后面会非常紧张。我当时有一道概率题算了5分钟还没结果就先跳过做完了所有情景题最后回过来才解出来。事实证明这个策略是对的因为后面有几道送分题没有失分。8. 笔试后的复盘与面试准备8.1 笔试后多久出结果携程的笔试结果一般在一周内通过邮件或短信通知也可能在招聘官网的申请状态中更新。我在考完后第三天就收到了面试邀约速度和效率都比较高。如果一周没收到基本就是挂了但也不用太焦虑春招批次多后面还有别的机会。收到面试邀约后会要求选择一个面试时间。技术岗一般有两轮技术面加一轮HR面技术面里面试官会拿着笔试的题目记录提问比如“你笔试编程题里用的DP思想能再详细讲讲吗”所以笔试结束后一定要立刻复盘梳理每道题的思路尤其是编程题。我当时在复盘时把DP转移方程重新推导了一遍面试时被问到“如果数据量很大怎么优化”才能从容回答堆优化和线段树优化。8.2 针对笔试查漏补缺笔试结束当天我把自己做错或不确定的题全部记在一张表格里标注考点和正确答案然后逐个知识点进行补漏。比如我发现自己对数据库隔离级别的理解不够细致就专门找了MySQL的锁和MVCC资料啃了一遍对Linux的netstat和ss命令不熟就在本地虚拟机反复练习。这种以考促学的方式效率比漫无目的地刷书高很多。如果你时间充裕建议再刷一刷往年携程及其他互联网公司的笔试真题。尤其是编程题重点刷区间DP、背包、拓扑排序、最短路径。不要把过多时间浪费在冷门算法上因为笔试很少考AC自动机、后缀数组等。8.3 技术通用岗面试与笔试的关系技术通用岗相对特别往往不会在笔试后就明确具体部门而是面试后再分配。这意味着笔试成绩只是敲门砖面试表现才是决定你最终去哪个团队的关键。所以笔试时不必过于追求某道题满分能够进入面试即可。面试时更看重你的思路、项目经历、基础能力和学习潜力。不过笔试成绩高确实能让你在排序中有优势。有些部门会优先选笔试成绩好的候选人所以能考高分就尽量考高分。不能的话至少保证基础题不丢分、编程题AC一个这就已经超过大多数人了。9. 关于携程笔试的个人经验总结写到这里我自己又把这场笔试复盘了一遍。总的感觉是携程技术通用岗的笔试难度处于互联网大厂春招的中等水平没有特别偏、怪、难的题但非常考验基础是否扎实以及是否能把经典算法快速“翻译”成业务场景。只要在大学期间认真上过数据结构、操作系统、计算机网络和数据库的课再抽一周时间刷题通过笔试是大概率事件。我个人的建议还是那几点第一编程题一定要先写思路再写代码别一上来就敲第二选择题读题要细心多选题不确定就不选第三合理安排时间先编程、后选择、再智力题第四考完立刻复盘做好和面试官谈笑风生的准备。希望这份经验能帮你少踩一些坑顺利通过携程的笔试拿到心仪的offer。