用友笔试第二场：四道编程题复盘

《面试题目》

1. 给一个重量数组和每天能运送的重量上限，必须按顺序搬物品且不能超过每日上限，求最少需要多少天。
2. 纯 IO 模拟：给一段配置，输出这段配置对应的节点流转。例如输入

   A 1
   B 2
   C 2
   D 3

   要输出

   start->A
   A->fork_1
   A->fork_2
   fork_2->B
   fork_3->C
   B->join_1
   C->join_1
   join_1->D
   D->end

3. 解析 JSON 后处理业务：时间区间合并。
4. 解析 JSON 后处理业务：有向图相关。

原帖复盘：第 1 题是签到题，AC；第 2 题调了半天「给我调力竭了」；第 3、4 题给的解析器代码不能复制、题目详情页的表格显示不全，只能手动输入；好处是这几题都能用测试用例骗到分。

《参考解析》

第一题：二分答案 + 贪心校验

题目是经典模型：物品必须按顺序搬运、每天总重量不超过上限，求最少天数。因为天数与「每天上限」的关系单调（上限越大天数越少），可以对天数做二分，也可以用更直接的思路——顺着原数组贪心累加，超过上限就开新的一天：

def min_days(weights, cap):
    days, cur = 1, 0
    for w in weights:
        if w > cap:          # 单个物品就超上限，无解
            return -1
        if cur + w > cap:
            days += 1
            cur = w
        else:
            cur += w
    return days

复杂度 O(n)。如果题目反过来给「天数」求「最小运载能力」（LeetCode 1011 的形态），就用二分答案 + 上面的贪心做 check：二分 cap 落在 [max(weights), sum(weights)]，对每个 mid 用 O(n) 校验天数是否 ≤ 给定值，总体 O(n log sum)。这类题有三个易错点：① 单个物品超过上限时的处理（返回无解还是允许当天只搬它）；② 天数从 1 开始而不是 0；③ 边界取 left = max(weights) 而不是 0，否则会死循环或算错。

第二题：fork/join 结构的输出模拟

这题是纯模拟，考的是把语义读懂并准确落地。从示例可以看出模型：配置里的第二个数字是层级/深度，同一层的节点会分叉成 fork_n，多个分叉在下一层汇合时产生 join_n，最后接 end。这类题的通用做法：

1. 按层级分组：读入所有 (名称, 层级)，按层级分桶，同时保留输入顺序。
2. 建立流转关系：start 连到第一层节点；一个父节点若有多个子节点，就生成 fork_1…fork_k（编号全局递增，示例里 A 的两个分叉是 fork_1、fork_2，C 用的是 fork_3），子节点分别接在各自的 fork 后面；多个子节点汇到同一个下一层节点时生成 join_n，由 join_n 连到该节点（示例里 B、C 汇到 join_1，join_1 再连 D）。
3. 处理最后一层：最后一层的节点直连 end。
4. 逐行输出，注意换行与顺序（是不是按生成顺序、是否按层级排序），最后一行是否要换行。

调试建议：把示例输入硬编码进本地脚本先跑通，再改成读标准输入；输出用 '\n'.join(lines) 一次性打印，避免多次 print 带来的格式差异。原帖说「调半天给我调力竭了」，通常就是踩在编号规则（fork/join 的计数是全局的还是每层重置）和输出顺序上——这两点必须拿题目示例反推验证。

第三题：时间区间合并

和前一场的合并区间是同一类题，只是输入变成 JSON 里的时间对象。步骤固定：

1. 解析：把 JSON 里的时间字段读出来，统一转成可比较的形式。时间最好转成时间戳或 (时, 分) 元组再比较，直接比字符串只在格式完全一致时可靠。
2. 排序：按开始时间升序。
3. 扫描合并：if cur.start <= last.end: last.end = max(last.end, cur.end)，否则开启新区间。必须取 max，否则被包含的区间会把右端点缩小。
4. 输出格式：按题目要求还原成时间字符串，注意补零（09:05 vs 9:5）、跨天区间、以及边界相接（09:00-10:00 与 10:00-11:00 是否算重叠）这几处细节。

第四题：有向图常见考点

「JSON 输入 + 有向图」的题型无非几种，先把可能的考点列全，读题时对号入座：

• 拓扑排序：判断能否排出一个合法顺序（有环则不能），用入度数组 + 队列（Kahn 算法）；要求按字典序输出就用优先队列。
• 环检测：DFS 三色标记（白/灰/黑）或并查集（无向图），有环时报出环上节点。
• 可达性/路径：BFS/DFS，或 Floyd、Dijkstra（带权最短路）。
• 连通分量/关键路径：并查集或 Tarjan（强连通分量），项目排期类题目会问最长路径（关键路径法，可用拓扑序上 DP）。
• 节点与边的建模：注意 JSON 里可能给的是边列表、邻接表或父子关系，要先转成统一的邻接表再算；节点 id 可能是字符串，需要先映射成下标。

笔试环境的坑：题目不能复制、表格显示不全

原帖遇到的两个环境问题是很多在线笔试的通病，且都有应对办法：

• 解析器代码不能复制：如果允许开本地编辑器，就先手敲一小份最小解析器（或者自己写十几行 JSON 解析/tokenize）在本地调试；也可以只把输入样例敲进本地文件，逻辑写完再贴回在线环境。
• 详情页表格显示不全：把浏览器缩放调小、或用开发者工具改样式/直接看接口返回；也可以截图后放大看。别凭猜测做题，规则错一个字整题就废。
• 善用「骗分」：原帖明确说这几题都能用测试用例骗分——意思是把题面给出的样例直接判断输出，或者对部分输入范围写特判，先拿下部分用例。这是合规且高效的策略：先把分数锁住，再优化通用解。