启云方笔试：3 道编程题，模拟 + 字符串 + 二分答案

《面试题目》

1. 第一题（100 分，模拟）：给出一组字符串记录，每条含 ID、时间、距离、注册号、实际注册号五个字段，如何找出注册号与实际注册号不一致的记录，并在同一个 ID 内找出「时间相差小于 60 分钟且距离大于 5KM」的两条记录？
2. 第二题（100 分，字符串处理）：给定一个由大小写字母和其他任意字符组成的字符串，对每个下标位置判断——如果该字符属于一段连续重复字符，就以这段的连续字符数为结果；如果是单个字符，就以该字符在后续整个字符串中剩余的个数为结果。最后按个数降序、个数相同时字母序升序，以「字母 + 个数」的形式输出全部结果，怎么实现？
3. 第三题（200 分，二分答案 + 图）：给定一张图，定义一条路径的权值为这条路径上经过节点的最小权值，如何求出从 (0,0) 到 (n,m) 的所有路径中，这个最小权值的最大值？

《参考解析》

第一题：分组的边界比筛选条件更容易漏

先把记录解析成结构体、按 ID 分桶，再在桶内比较。原帖作者卡在「总是不对」，最典型的漏法是只比较排序后的相邻两条：题目要求的是同一个 ID 下任意两条记录满足条件，差值为严格小于 60 分钟、严格大于 5KM，等于边界的那组不算。还要处理桶内不足两条、时间字段需要先解析成可比较的量（统一到分钟或时间戳）、距离带单位等细节。比较前把「同一 ID 内两两组合」写成双重循环，规模小时不必急着优化。

第二题：连续段一次算完，单字符靠全局词频

顺序是先把整个字符串的字符出现次数统计出来，再从左往右扫：遇到 s[i] == s[i+1] 就一路吃到底，输出段长并把这一段跳过去；否则说明是单字符，输出该字符的剩余计数。计数用哈希表，扫描时同步扣减，就不需要回头再数一遍。真正丢分的是输出约定——大小写是否算同一个字符、非字母字符参不参与、排序时「个数降序 + 字母序升序」的字母序按 ASCII 还是按字符集，都要照题面样例逐字对齐。原帖两个模拟题都只拿到部分分，正说明这类题的风险在读题与格式，不在算法。

第三题：最大化最小值，二分答案定界，BFS 判连通

「使路径上的最小值最大」是最大化最小值的标准形状，答案具有单调性：某个阈值可行，比它小的阈值一定也可行。于是二分这个阈值 x，每次只保留权值不小于 x 的节点（起点终点本身也要过这一关），从 (0,0) 做一次 BFS 看能否到达 (n,m)，能就把下界抬上去，不能就把上界压下来。二分的上下界直接取全图节点权值的最小值与最大值，避免拍脑袋定范围。单次判定是 O(V+E)，总复杂度 O((V+E)·log W)，比枚举路径或改造最短路清爽得多；要留意的是节点权值还是边权值，本题定义在节点上，判定时过滤的是可以走的点。

笔试这一关在筛什么

模拟题的分数差异几乎全部来自工程细致度：读题时先把输入格式、输出格式、边界条件抄成清单，写之前用样例手算一遍预期输出，写完再自造最小规模、重复值、临界值三组数据。时间分配上，两道 100 分题优先做干净，200 分题先写能过样例的暴力版本保底，再去想二分 + BFS 这类正解。部分分是可以主动拿的——把格式化输出和边界写对，往往比多调 20 分钟算法更划算。