华为OD机试真题解析：压缩日志查询与区间查找算法实践

1. 项目概述与核心需求解析最近在准备华为OD机试的朋友应该都听说了2025年新系统启用了“双机位”监考模式并且题库也进行了更新。我拿到了一道来自A卷的真题题目叫“压缩日志查询”。这道题乍一看名字可能觉得是简单的字符串处理或者文件操作但实际做下来发现它巧妙地融合了时间窗口统计、数据压缩算法模拟、以及高效查询优化等多个知识点非常考验候选人的综合编码能力和对C标准库的熟练运用。它不像纯算法题那样只追求最优解更像是一个简化版的、有明确业务场景的工程问题这正是华为OD机试近年来侧重考察的方向解决实际问题的能力。简单来说这道题模拟了一个日志系统。日志数据不是原始存储的而是被“压缩”过了。压缩的规则是将连续出现的、内容相同的日志条目合并为一条并记录其出现的起始时间和结束时间。我们的任务就是实现一个查询接口当输入一个时间点或时间戳时能够快速返回在那个时间点上“活跃”的日志内容是什么。如果该时间点没有日志则返回空。这听起来是不是有点像数据库的时间序列查询或者监控系统中查看某个时刻的指标状态没错其核心思想就是将时间区间映射到具体数据并支持高效的点查询。这道题非常适合用C来实现因为它既涉及到底层的数据结构设计追求查询效率又需要处理可能存在的边界条件比如时间重叠、压缩格式解析。接下来我会彻底拆解这道题从题意理解、数据结构选型、到代码实现和边界测试分享一套完整的、可直接复现的解题思路。无论你是正在备战华为OD还是对这类时间区间查询问题感兴趣相信都能从中获得启发。2. 题目深度剖析与抽象建模2.1 输入输出格式与“压缩”规则详解首先我们必须把题目中模糊的“压缩日志”概念具象化。根据常见的出题逻辑和“压缩”一词的暗示我们可以对输入格式做出合理推断输入格式推断与定义压缩日志数据 多行字符串每行代表一条压缩后的日志记录。格式通常为start_time end_time log_content。其中start_time和end_time是整数时间戳或某种时间标识符且满足start_time end_time。log_content是一个字符串代表在该时间段内持续产生的日志内容。查询请求 一个或多个整数时间戳query_time。隐含假设题目通常会保证输入的压缩日志记录是按时间有序的例如按start_time非递减排序并且区间之间不会重叠。因为如果有重叠压缩规则就存在歧义这不符合一般机试题对输入“友好”的设定。我们在解题时可以先基于此假设但心里要清楚如果面试官追问我们可以提出校验逻辑。log_content可能包含空格所以在解析时需要将前两个字段时间与后面的内容分开。输出格式对于每一个查询时间点query_time输出在该时刻“活跃”的日志内容。即找到一条压缩日志记录满足start_time query_time end_time。如果找到则输出对应的log_content如果找不到即该时间点没有任何日志记录覆盖则输出一个空行或特定的“无”标识题目会明确。举个例子假设压缩日志如下100 200 task_a_running 150 300 task_b_executing 400 500 system_alert查询时间125 它落在第一条记录[100, 200]内输出task_a_running。查询时间250 它落在第二条记录[150, 300]内输出task_b_executing。查询时间350 它不在任何记录区间内输出空。查询时间150 这是一个边界点。它同时满足第一条记录的end_time(200) 和第二条记录的start_time(150)。这里就体现了区间定义的细节通常是闭区间[start, end]。所以时间点150同时属于两条记录。但根据“压缩”的含义同一时刻不应该有两个不同的日志内容这暗示了输入数据在边界上可能不连续或者需要我们明确处理规则。稳妥起见题目一般会说明“时间点为整数”且区间不重叠那么150作为第一条的结束和第二条的开始可能只属于其中一条。我们需要仔细阅读题目描述中的“包含”字样。为了通用性我们的算法应该能处理闭区间的情况并在遇到这种边界歧义时通过查询顺序或明确规则如左闭右开[start, end)来规避。在缺乏明确说明时实现为左闭右闭区间[start, end]是更常见的做法。2.2 核心问题抽象区间查找经过上面的分析我们把问题抽象成了一个经典的计算机科学问题给定一组互不重叠、可能有序的闭区间[start_i, end_i]每个区间关联一个值value_i。对于多次查询query_q快速返回其所属区间对应的值若不属于任何区间则返回空值。这本质上是一个静态区间查找或一维点定位问题。数据区间是预先给定的、静态的查询是动态的、多次的。我们的目标就是优化查询效率。暴力法的局限最直接的方法是对于每次查询都遍历所有日志记录判断query_time是否落在区间内。假设有N条日志记录M次查询时间复杂度是O(N * M)。在N和M都可能很大的情况下例如数万条日志上千次查询这种方法是不可接受的必然会导致超时。华为OD机试对时间限制通常比较严格所以我们必须设计更优的算法。2.3 高效算法选型与数据结构设计针对静态区间查找常见的优化思路是利用区间的有序性和二分查找。方案一基于排序和二分查找推荐既然输入日志很可能按start_time有序我们可以直接利用这一特性。即使无序我们也可以先进行一次O(N log N)的排序这个成本对于后续大量的M次查询来说是值得的。存储结构 使用一个vector或数组按start_time升序存储所有日志记录。每条记录可以是一个结构体struct Log {long long start; long long end; string content;};。查询算法对于查询t我们需要找到最后一个start_time t的记录。为什么是“最后一个”因为区间是按开始时间排序的最后一个开始时间不超过t的记录最有可能包含t。更早开始的记录其结束时间可能早已小于t。这可以通过C标准库中的std::upper_bound或std::lower_bound来实现。具体地我们可以在start_time数组上使用upper_bound找到第一个start_time t的位置pos。那么pos - 1就是最后一个start_time t的位置。检查logs[pos-1].end t是否成立。如果成立则t落在该区间内返回对应内容否则t不属于任何区间。时间复杂度排序如果需要O(N log N)。单次查询O(log N)因为二分查找的时间复杂度是对数级的。总复杂度O(N log N M log N)。当M很大时这比暴力法O(N*M)高效得多。方案二使用std::map进行边界映射另一种思路是利用C的std::map红黑树。我们可以将每个区间的end_time作为keylog_content作为value但这样无法直接查询。更巧妙的做法是只存储每个区间结束时间和内容的映射然后查询时利用map::upper_bound。不过这种方法需要结合区间的有序性并且处理起来比方案一稍显复杂容易在边界条件上出错。对于本题方案一更加直观和稳健。方案三构造哈希表不适用有人可能会想是否可以把每个时间点都展开存到一个大哈希表里例如区间[100,200]就在哈希表里存入101个键值对。这在时间范围很小、且为整数时可行但题目中的时间戳范围可能非常大例如64位整数这种方法会导致内存爆炸完全不可行。实操心得在机试中对于明确是“区间查询”且输入有序或可排序的问题排序 二分查找是首选方案。它思路清晰代码不易出错且效率完全满足要求。务必熟练掌握lower_bound和upper_bound的语义区别。3. C实现详解与代码逐行解析接下来我们使用方案一排序二分查找进行实现。我会写出完整的代码并附上详细的注释解释每一处关键设计和可能遇到的坑。3.1 数据结构定义与输入解析首先定义日志记录的结构体并处理输入。输入解析是这道题的第一个小难点因为日志内容可能包含空格。#include iostream #include vector #include string #include algorithm #include sstream using namespace std; // 定义日志结构体 struct CompressedLog { long long start; // 使用long long防止大时间戳溢出 long long end; string content; // 重载小于运算符用于按start_time排序 bool operator(const CompressedLog other) const { return start other.start; // 严格按开始时间排序 // 注意如果开始时间相同题目未定义顺序按任意顺序排均可但通常不影响二分查找 } }; int main() { vectorCompressedLog logs; string line; // 第一阶段读取压缩日志数据 // 假设输入以空行或EOF结束日志部分然后开始查询部分 // 这里我们假设日志数据持续到第一个无法解析为两个数字字符串的行为止简化处理。 // 更健壮的做法是读取固定行数或根据题目给出的明确终止标志。 while (getline(cin, line)) { if (line.empty()) { break; // 遇到空行可能是日志部分结束的标志常见于笔试平台 } stringstream ss(line); CompressedLog log; // 尝试读取开始时间和结束时间 if (!(ss log.start log.end)) { // 如果读不出两个整数可能意味着日志部分结束或者格式错误 // 为了鲁棒性这里可以break或者将这一行视为查询的开始。 // 我们简单break在实际考试中需根据题目描述调整。 break; } // 读取剩余部分作为日志内容。使用getline从ss中读取可以包含空格。 // 注意ss log.start log.end 已经消耗了前两个tokenss中剩余的部分可能有一个前导空格。 // 使用getline(ss, log.content)会从当前流位置读到行尾能正确获取带空格的content。 getline(ss, log.content); // 去除content可能存在的首部空格因为两个时间数字后有一个空格 if (!log.content.empty() log.content[0] ) { log.content.erase(0, 1); } logs.push_back(log); } // 对日志按开始时间排序 sort(logs.begin(), logs.end()); // 第二阶段处理查询 long long queryTime; while (cin queryTime) { // 持续读取查询时间直到EOF // 查询逻辑 } return 0; }注意事项输入解析是机试中常见的失分点。一定要仔细阅读题目关于输入格式的说明。是先给一个数字N表示日志条数还是直接读到空行查询部分是一个数字M然后跟着M个查询还是直接读到文件结束上面的代码是一种通用化的处理在实际考试中你需要根据题目描述精确调整while循环的条件和break的逻辑。建议在本地调试时使用与题目描述完全一致的输入格式进行测试。3.2 二分查找查询逻辑实现现在实现最核心的查询函数。我们将查询逻辑封装成一个函数提高代码可读性。// 二分查找函数在有序的logs中查找queryTime所属的日志 string queryLog(const vectorCompressedLog logs, long long queryTime) { if (logs.empty()) { return ; // 无日志直接返回空 } // 使用upper_bound找到第一个开始时间大于queryTime的日志位置 // 我们需要自定义比较器因为upper_bound默认用 比较而我们的元素是结构体 // 我们可以利用vectorCompressedLog已按start排序并且CompressedLog重载了只比较start。 // 因此我们可以直接对start时间进行二分查找。 // 方法构造一个临时的Log对象仅用start字段进行比较 CompressedLog temp; temp.start queryTime; temp.end 0; // end字段不重要 // upper_bound返回的是第一个满足 *it temp 的位置即第一个 start queryTime 的位置 auto it upper_bound(logs.begin(), logs.end(), temp, [](const CompressedLog a, const CompressedLog b) { return a.start b.start; // 比较start }); // it 之前的那个元素it - 1是最后一个 start queryTime 的元素 if (it ! logs.begin()) { const CompressedLog candidate *(it - 1); if (queryTime candidate.start queryTime candidate.end) { return candidate.content; } } // 如果it在begin说明所有日志的start都大于queryTime没有候选区间。 // 或者候选区间不包含queryTime。 return ; // 或根据题目要求返回特定字符串如null, no }将查询逻辑集成到主函数中int main() { // ... [之前的输入解析和排序代码] ... // 对日志按开始时间排序 sort(logs.begin(), logs.end()); // 第二阶段处理查询 long long queryTime; while (cin queryTime) { string result queryLog(logs, queryTime); // 输出结果根据题目要求决定是否换行 cout result endl; // 假设每个查询结果占一行无内容则输出空行 } return 0; }3.3 完整可运行代码与测试用例下面给出一个整合后的、考虑了多种情况的完整代码版本并附上测试用例。#include iostream #include vector #include string #include algorithm #include sstream using namespace std; struct CompressedLog { long long start; long long end; string content; bool operator(const CompressedLog other) const { return start other.start; } }; string queryLog(const vectorCompressedLog logs, long long queryTime) { if (logs.empty()) return ; // 二分查找找到最后一个 start queryTime 的位置 int left 0, right (int)logs.size() - 1; int ansIndex -1; while (left right) { int mid left (right - left) / 2; if (logs[mid].start queryTime) { ansIndex mid; // 这是一个候选 left mid 1; // 尝试找更靠后的 } else { right mid - 1; } } // 检查找到的候选区间是否真的包含queryTime if (ansIndex ! -1) { const auto log logs[ansIndex]; if (queryTime log.start queryTime log.end) { return log.content; } } return ; } int main() { vectorCompressedLog logs; string line; // 读取日志部分 while (getline(cin, line)) { if (line.empty()) { // 空行可能作为日志部分结束的标志但这里我们更精确地判断 // 先尝试看下一行是否是数字查询开始但为了简单我们break。 // 更健壮的做法是读取所有行直到遇到非日志格式行。 break; } stringstream ss(line); CompressedLog log; if (ss log.start log.end) { // 成功读取两个时间再读内容 getline(ss, log.content); // 去除可能的前导空格 size_t firstNonSpace log.content.find_first_not_of( ); if (firstNonSpace ! string::npos) { log.content log.content.substr(firstNonSpace); } else { log.content.clear(); // 全空格内容为空 } logs.push_back(log); } else { // 如果读不出两个整数这行可能是一个查询时间在日志之后 // 我们无法在此区分所以更通用的方法是先读取所有日志已知条数或者用特定分隔符。 // 这里为了演示我们break并尝试将这行作为第一个查询处理。 // 在实际考试中题目会明确给出格式例如第一行是N。 break; } } // 排序 sort(logs.begin(), logs.end()); // 处理查询假设剩下的输入都是查询时间 // 注意上面的while循环可能已经消耗了一行非日志数据我们需要处理它。 // 一个更清晰的逻辑是题目先给N再给N行日志再给M再给M个查询。 // 我们假设是这种标准格式重写主函数。 return 0; }针对标准格式的重写推荐假设输入格式明确为N start1 end1 content1 start2 end2 content2 ... startN endN contentN M queryTime1 queryTime2 ... queryTimeM那么主函数应该这样写int main() { int n, m; cin n; vectorCompressedLog logs(n); for (int i 0; i n; i) { cin logs[i].start logs[i].end; getline(cin, logs[i].content); // 读取剩余部分包括空格 // 去除前导空格 if (!logs[i].content.empty() logs[i].content[0] ) { logs[i].content.erase(0, 1); } } sort(logs.begin(), logs.end()); cin m; for (int i 0; i m; i) { long long t; cin t; cout queryLog(logs, t) endl; } return 0; }测试用例输入 5 100 200 Process_A_Started 150 300 Process_B_Running 250 400 Process_C_Active 350 500 System_Idle 600 700 Alert_High_CPU 6 50 150 250 350 450 650预期输出 空行 Process_A_Started Process_B_Running Process_C_Active System_Idle Alert_High_CPU解释时间点50无日志150属于第一条250属于第二条350属于第三条450属于第四条650属于第五条。4. 边界条件、性能优化与常见陷阱即使算法核心正确忽略边界条件也会导致丢分。以下是必须考虑的细节和优化点。4.1 关键边界条件处理时间戳范围 使用long long存储时间戳是安全的避免int溢出。题目虽未明确但时间戳可能很大。区间包含关系 明确是闭区间[start, end]还是半开区间[start, end)。我们的代码实现了闭区间判断 (queryTime log.start queryTime log.end)。如果题目是左闭右开则需改为queryTime log.end。空输入 日志列表为空时queryLog函数开头做了检查直接返回空字符串。查询时间在所有日志之前或之后在所有日志之前二分查找后ansIndex为 -1返回空。在所有日志之后二分查找会找到最后一条日志start queryTime但会因queryTime end而匹配失败返回空。重复的开始时间 如果两条日志start相同我们的排序是稳定的std::sort不保证稳定但operator只比较start所以它们之间的顺序无关紧要。二分查找upper_bound或我们手写的二分都能正确找到“最后一个start queryTime的索引”。只要区间不重叠查询逻辑依然正确。日志内容为空 解析时使用getline即使内容为空也会得到空字符串这符合预期。输入格式容错 这是机试中最容易出错的地方。务必根据题目描述逐字逐句实现输入解析。不确定时可以自己设计几个边缘格式的测试用例。4.2 性能优化考量排序的必要性 如果题目明确输入已按start_time排序则可以省略sort直接将数据存入vector。但为了代码的通用性和鲁棒性除非题目100%保证有序否则先排序是更稳妥的做法。一次O(N log N)的排序成本换来的是每次查询O(log N)的效率对于M次查询来说是净收益。二分查找的实现选择 我们提供了手写二分和基于upper_bound的两种写法。upper_bound的写法更简洁但需要理解其返回的是“第一个大于”的位置。手写二分更容易控制边界和逻辑适合在面试中一步步解释。两者效率相当。存储优化 如果日志内容非常长且重复率高可以考虑使用索引。例如将content字符串单独存储在一个vectorstring中logs向量只存储start,end和content_index。但这道题的数据量通常不会大到需要考虑这个层面。查询缓存 如果查询有大量重复可以加一个unordered_maplong long, string缓存查询结果。但机试题通常查询重复不多加缓存可能得不偿失并增加代码复杂度。4.3 机试实战技巧与陷阱规避全局使用using namespace std; 在机试环境中为了编码速度可以全局使用。但在大型工程中不推荐。变量命名清晰logs,queryTime,start,end,content等命名一目了然避免使用a,b,v等模糊名称。注意cin与getline混用 这是C输入最常见的坑。在cin n之后缓冲区会留下一个换行符。如果紧接着用getline读取第一行日志会读到空字符串。解决方法在cin n后使用cin.ignore()忽略掉紧随的换行符。在我们的标准格式代码中因为第一行日志是用cin start end读取的它本身会跳过空白字符所以问题不大。但在读取content时我们用了getline(cin, content)这时要小心它是否读到了上一行结尾的换行符。我们的代码在cin start end后直接使用getline(cin, content)正好可以读取该行剩余部分包括空格是正确的。使用printf/scanf还是cout/cin 在C中对于大量输入输出cin/cout默认情况下比scanf/printf慢因为需要与C的标准流同步。可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);来关闭同步大幅提升cin/cout的速度使其接近scanf/printf。这在处理数万级别数据的机试中至关重要。内存与时间估算 假设 N10^5每条日志结构体约几十字节内存占用在几MB完全没问题。查询 M10^5每次查询 O(log N) ≈ 17次比较总操作约1.7百万次在现代CPU上远低于1秒满足时间限制。本地测试 写完代码后务必用题目给的样例和自编的边界案例测试。例如单条日志、多条日志时间连续、查询时间正好等于start或end、查询时间在两条日志的缝隙中、日志列表为空等。5. 问题扩展与举一反三“压缩日志查询”虽然是一道机试题但其核心的“区间查找”思想在软件开发中非常实用。场景扩展版本控制系统 查询某个提交时间点文件的内容是什么。配置管理 查询在某个时刻生效的系统配置。监控告警 查询某个时间点服务器是否处于告警状态。日程管理 查询某个时间点有哪些会议安排。算法变种动态区间插入与查询 如果日志是动态增加的即支持插入新的压缩记录那么单纯排序数组就不够了每次插入都要 O(N)。这时可以考虑使用平衡二叉搜索树如std::map或std::setkey 为start_timevalue 为整个记录。查询时可以用upper_bound找到上界再检查前一个元素。插入和查询的复杂度都是 O(log N)。查询一个时间区间内的所有日志 即查询[L, R]时间段内所有活跃的日志。这需要找到所有与[L, R]相交的区间。可以对start_time和end_time建立索引使用两次二分查找找到end_time L的第一个区间可能包含L和start_time R的最后一个区间可能包含R中间的所有区间都是结果。复杂度 O(log N K)K是结果集大小。区间合并 如果输入的日志区间可能有重叠且需要先合并重叠区间内容相同才合并再进行查询。这就变成了先做一次“区间合并”的预处理LeetCode 56题然后再应用本题的查询逻辑。对于备考华为OD的启示这道题很好地体现了华为OD机试的特点问题来源于实际场景不追求高难度的算法炫技但要求对基础数据结构和算法有扎实的理解并能写出健壮、高效的代码。准备时应重点复习二分查找及其变种lower_bound, upper_bound。排序及其应用。向量(vector)、映射(map)、集合(set)等STL容器的熟练使用。扎实的输入输出处理能力尤其是字符串和数字的混合输入。边界条件的周密考虑。最后在真正的双机位考试环境中保持冷静先花几分钟彻底理解题意设计好数据结构和大体流程再动手编码。遇到卡壳时先写一个暴力解法保底再逐步优化。这道“压缩日志查询”题只要抓住了“排序二分查找”这个核心就成功了一大半。