单位转换这个题目很多人第一眼觉得简单无非就是乘个系数。但真上手做3528. 单位转换 I这道题或者在公司里处理SAP BOM物料单位转换的时候你会发现事情完全不是查个表这么简单单位之间的换算关系是稀疏的链条可以是多跳的比率还可能互相矛盾。这篇文章我把算法题的解法思路和ERP里的真实业务场景放在一起拆你会发现它们本质上是同一个问题在一张带权图上从起点单位走到终点单位把路径上的换算因子乘起来。如果你正在刷题准备面试或者刚好在做物料主数据、BOM相关的开发这篇内容可以直接帮你把会做算法题和能处理业务问题这两件事打通。1. 把单位转换当做一个图问题来解1.1 题目到底在问什么这类单位转换题目的标准输入模式是这样的给你一组已经知道的换算关系比如1 米 100 厘米1 千米 1000 米1 英尺 12 英寸然后给你一些查询问你某个单位到另一个单位的换算系数是多少。比如1 千米等于多少厘米答案就是 1000 × 100 100000。题目名字里有个I说明这是系列题的第一题通常考察的也就是最基础的单路径换算。千万不要被基础两个字骗了基础题反而最考验你对图结构的敏感度因为后续的IIIII往往就是在这上面加循环检测、加多源查询、加矛盾处理。我最早做这类题的时候第一反应是维护一个大的换算字典把所有直接给出的关系都塞进去查询的时候直接查。结果一遇到公里转厘米这种需要中间经过米的查询就傻眼了。所以核心点在于题目给你的换算关系是离散的但查询是任意的你必须把离散关系组合成一条可达路径。1.2 为什么第一反应是建图而不是查表你可能会问为什么不直接把所有可能的单位对都预处理出来比如已知米到厘米、千米到米那就手动算出千米到厘米存起来。这个思路在小数据集上没问题但一旦单位种类变多比如几百个单位全量两两组合就是几万条记录维护成本极高而且新增一个单位就要全量重算。更麻烦的是很多单位之间根本没必要提前算属于典型的用空间换时间但换不划算。所以正确的方式是把每个单位当成图的节点把换算关系当成带权有向边节点单位比如 meter、centimeter、km边从 A 指向 B权重为1个A等于多少个B查询从起点节点出发找到一条路径到终点节点路径上所有边的权重相乘用图的好处很明显新加一个单位只需要加一个节点和几条边查询的时候动态算路径就行。这跟你平时用导航软件找路线是一个道理你不会把全世界所有两地之间的路程都提前存下来而是实时用图去算。2. 核心算法设计与选型2.1 DFS/BFS单点查询的暴力解法最简单直接的方案是每次查询的时候从起点开始做深度优先搜索DFS或者广度优先搜索BFS沿着已知的换算边一层层往外走直到走到目标单位。DFS的写法比较符合直觉它的核心就是一个带当前累积换算系数的递归def dfs(cur, target, acc, visited): if cur target: return acc visited.add(cur) for neighbor, rate in graph[cur]: if neighbor not in visited: result dfs(neighbor, target, acc * rate, visited) if result is not None: return result return None注意几个关键点acc是走到当前节点时已经累积的系数从起点出发是 1。每次经过一条边 A→B权重 rate新的累积值就是acc * rate含义是1个起点单位等于 acc 个当前单位。visited必须记录已经访问过的节点防止图里有环导致死循环。这个题虽然表面上没有说有没有环但工程上默认按有环处理最稳妥。返回值用None表示不可达不要用 0因为有些换算结果本来就可能很小0 会跟不可达混淆。BFS 的思路类似只不过用队列代替递归栈好处是不会爆栈坏处是要自己维护每一层携带的累积值。在单位数量不大的情况下两者差别不大我一般优先 DFS代码更短。如果你的环境对递归深度有严格限制再切 BFS。2.2 预处理全量关系Floyd-Warshall如果查询特别多而且单位全集是已知的每次查询都 DFS 一遍会重复计算。这时候有一个更优雅的做法用 Floyd-Warshall 算法一次性把所有单位对之间的换算系数都算出来。核心逻辑是三层循环枚举中间单位 k尝试用i→k 的系数 × k→j 的系数来缩短或者补全 i→j 的路径n len(units) dist [[None] * n for _ in range(n)] # 初始化直接已知的换算关系填入 dist for i in range(n): dist[i][i] 1.0 for a, b, rate in conversions: dist[index[a]][index[b]] rate dist[index[b]][index[a]] 1.0 / rate # Floyd-Warshall for k in range(n): for i in range(n): if dist[i][k] is None: continue for j in range(n): if dist[k][j] is None: continue if dist[i][j] is None or dist[i][k] * dist[k][j] dist[i][j]: dist[i][j] dist[i][k] * dist[k][j]这里dist[i][j]的物理含义就是1个单位i等于多少个单位j。初始化的时候别忘了对角线是 1还有反向边是正向边的倒数——这是新手特别容易漏的一步。Floyd-Warshall 的复杂度是 O(n³)单位种类几百个的时候完全能接受。这个方案的优点很突出预处理完之后任何查询都是 O(1)而且因为所有中间路径都已经被融合过代码逻辑也最简单。缺点就是空间 O(n²)以及新加单位需要重新全量计算。2.3 加权并查集另一种巧解还有一个在很多刷题笔记里被低估的方案就是加权并查集Weighted Union-Find。它的核心思想是并查集维护连通性权重维护比例关系。每个节点不仅记录自己的父节点还记录自己到父节点的换算系数。find 的时候做路径压缩同时把权重沿着路径累乘。这样同一棵树内的任意两个节点都能通过分别到根节点的系数相除得到彼此的换算系数。查一段核心代码你就明白了class WeightedUnionFind: def __init__(self): self.parent {} self.weight {} # 节点到父节点的换算系数 def add(self, x): if x not in self.parent: self.parent[x] x self.weight[x] 1.0 def find(self, x): if x not in self.parent: return None, None if self.parent[x] ! x: root, w self.find(self.parent[x]) self.weight[x] self.weight[x] * w self.parent[x] root return self.parent[x], self.weight[x] def union(self, a, b, rate): self.add(a); self.add(b) ra, wa self.find(a) rb, wb self.find(b) if ra rb: return # 让 ra 的根指向 rb并修正权重 self.parent[ra] rb # 1个a rate 个b # a到ra的权是wab到rb的权是wb # wa * new rate * wb new rate * wb / wa self.weight[ra] rate * wb / wa查询 x→y 时先分别 find 得到(root_x, wx)和(root_y, wy)如果根相同答案就是wx / wy。加权并查集的好处是合并关系的同时完成了路径压缩后续查询接近 O(1)而且天然支持动态添加换算关系。坏处是理解门槛比 DFS 高一点union 时那条权重公式容易算错方向。我的经验是如果你不熟悉这个套路面试时写 DFS 就够了但工程代码里加权并查集的性能优势很明显。2.4 三种方案的取舍对照我直接把这些方案在真实场景下的表现整理成一张对比表方便你按需求选方案单次查询复杂度预处理复杂度代码难度适合场景DFS/BFSO(VE)无低查询少、单位少、临时算Floyd-WarshallO(1)O(n³)低查询极多、单位全集固定加权并查集近似O(1)O(α(n))中动态添加换算关系、查询频繁说实话笔试面试里 90% 的情况用 DFS 就能过Floyd-Warshall 是想秀一下或者查询量巨大时的加分项。真到了 SAP 这种企业级系统里我反而更推荐加权并查集原因后面讲业务的时候细说。3. 实操实现与代码拆解3.1 数据结构的定义不管选哪种算法第一步都是把输入转换成图结构。这步做得干净后面所有算法都能直接套。我习惯用一个字典嵌套字典的结构graph {} def add_edge(a, b, rate): graph.setdefault(a, {})[b] rate graph.setdefault(b, {})[a] 1.0 / rate为什么要同时加反向边因为换算关系是双向的你知道1米100厘米就必然知道1厘米0.01米。如果你只存单向边查询方向一旦反了就找不到路。这不是优化是必须。如果你处理的是 SAP 里的单位转化率还要额外注意一点很多 ERP 系统里只存正向因子比如物料主数据里1箱12个就只存一个转换因子反向靠代码除以得到。这个不是错但你在设计数据结构时要提前约定好。3.2 核心代码实现下面给一个完整的 DFS 解法输入格式假设为conversions一组(from_unit, to_unit, rate)元组表示 1 个from_unit等于rate个to_unitqueries一组(from_unit, to_unit)元组返回值每个查询的换算系数无法换算返回None或者题目要求的 -1def calc_units(conversions, queries): graph {} for a, b, rate in conversions: graph.setdefault(a, {})[b] rate graph.setdefault(b, {})[a] 1.0 / rate def dfs(cur, target, acc, visited): if cur target: return acc visited.add(cur) for nxt, rate in graph.get(cur, {}).items(): if nxt not in visited: res dfs(nxt, target, acc * rate, visited) if res is not None: return res return None results [] for src, dst in queries: if src not in graph or dst not in graph: results.append(None) continue results.append(dfs(src, dst, 1.0, set())) return results这段代码有四个细节我专门提一下第一起点或终点不在图里的时候直接返回不可达不要跑 DFS 再碰壁减少无谓开销。第二visited每次查询都要新建一个set否则上一次查询的路径会把这次查询的口子堵死。第三递归终止条件放在最前面这样起点等于终点的查询比如千克到千克能直接得到 1.0这个语义很关键。第四浮点数相乘会有精度问题这个放后面单独说。3.3 边界条件与细节处理处理这类题目大部分坑不在算法本身而在边界条件。我罗列一下我自己踩过的和见过别人踩的单位名大小写。题目可能给你Meter和meter你直接当不同节点处理结果死活查不到。解决方式是统一转小写或者统一别的规范再入图。重复输入换算关系且数值矛盾。比如先给1米100厘米又给1米200厘米。处理方法分两种题目没明确时一般以后出现的为准或者保留先出现的。业务系统里则必须告警因为这是数据质量问题。间接换算的累计误差。路径越长浮点误差越大。这个在算法题里通常能过但 ERP 里算金额和库存会出大问题后面我们有专门一节讲。除零与负系数。换算率如果是 0 或者负数直接拒绝这条边这在物理世界里没有意义在数据清洗阶段就该剔掉。4. 真实业务场景SAP BOM物料单位转换4.1 为什么ERP里单位转换这么重要你可能觉得算法题就是算法题但3528. 单位转换 I这个编号能跟单位转换这个热搜词绑在一起恰恰说明它是从真实业务里抽出来的题。我在企业里做过物料主数据和 BOMBill of Materials物料清单相关的开发可以负责任地告诉你单位转换是 SAP 这类 ERP 系统里最容易出事故的环节之一。举个最典型的例子一张 BOM 里有 A 物料它的基本单位是千克但是在某个工序里需要按个发料在另一个工序里按箱计算。这时候系统就必须靠单位转换逻辑把 BOM 行项目上的数量从个换算成基本单位千克才能扣库存。一旦换算因子错了轻则库存账实不符重则生产缺料或者超耗。很多业务顾问天天挂在嘴边的物料单位转换指的就是这套机制。它不是简单的1吨1000千克这种常识换算而是物料特有的、基于物料属性维护出来的换算关系比如1箱12个、每件商品净重2.5千克。4.2 SAP的单位转换机制SAP 里单位转换大体上分三个层次理解了这三个层次你就知道为什么前面说算法题是它的抽象了第一层是基础计量单位。每个物料主数据里都有一个基本单位Base Unit of Measure这个单位是库存管理、成本核算的基准所有其他单位最终都要换算到它。第二层是替代计量单位。物料可以维护多个替代单位比如箱托盘个。算 BOM 数量、采购数量时可以用替代单位录入但系统会把它换算成基本单位去更新库存。第三层是换算因子。SAP 里换算关系通常是1 个替代单位 X 个基本单位这种形式而且分两类一类是固定的换算比例比如1米100厘米另一类跟物料属性相关比如1件2.5千克这里 2.5 是在物料主数据的附加数据里维护的。你看SAP 的这套机制和算法题里的conversions 输入几乎一一对应单位是节点换算因子是带权边查询就是某个单位等于多少基本单位。区别在于算法题通常给你一个无环的、一致的关系集合SAP 里环和矛盾是常态比如 A→B→C→A 的循环换算或者同一对单位在不同工厂维护了不同因子。算法题查询量小SAP 里 MRP 跑一次要换算几百万行 BOM 数量性能要求完全不同。算法题用浮点能接受的误差SAP 里库存数量和金额常常要求精确到小数后三位超了就锁账。4.3 从算法题到业务代码的思维迁移我自己在做一个单位换算微服务的时候就真的参照了加权并查集的思路这个服务的输入是物料主数据导出的换算关系输出是给 BOM 展开和 MRP 计算用的全量换算因子表。我当时的做法是先把所有换算关系加载进内存用加权并查集维护连通分量。每个物料取其基本单位作为根动态查询时从当前单位找到根再除以目标单位到根的系数。如果一个换算关系跟已有关系矛盾不是覆盖而是把新关系记入待处理队列等人工确认后再刷新缓存。这套设计最大的好处是新增一个换算关系只需要一次 union不需要像 Floyd-Warshall 那样全量重算。换算出错的时候也能通过连通分量快速定位到是哪条边的因子错了排查效率比在几百个单位的全量表里找快得多。这也回答了一个常见疑问算法题里的最优解到底有没有工程价值我的答案是有但需要结合业务约束去改造。纯粹 DFS 在业务里跑肯定不行但加权并查集、路径压缩这些思想稍微封装一下就是一套很稳的单位换算引擎。5. 常见问题与实战排查5.1 精度丢失与浮点比较单位换算用浮点数是逃不掉的但浮点有一个经典问题0.1 0.2不等于0.3。换算因子乘了一路误差会一点点累积起来。我在算法题里习惯这样处理判断结果是否相等时不用而是用abs(a - b) 1e-9。这个阈值不要太小也不要太大1e-6到1e-9之间比较合适具体看题目要求的精度。到了 SAP 业务场景单靠浮点阈值是不够的。库存数量通常用十进制精确类型类似 DECIMAL来算换算因子如果是1箱12个这种整数比例还好如果出现1件2.5千克这种小数乘以数量后再四舍五入就会碰到多出来的0.0001这种对账差异。业界的常规做法是换算时统一用高精度十进制运算到最后一步再按物料的数量小数位舍入并且把舍入差异记到差异科目里不让它凭空消失。5.2 循环换算与不一致比率算法题里最怕输入里有环比如 A→B→C→A。DFS 有visited防死循环但环本身还带一个隐患从 A 出发绕一圈回到 A算出来的系数未必是 1。比如 1A2B1B3C1C0.4A绕一圈就是 2×3×0.42.4不是 1。这说明输入关系自相矛盾。业务系统里出现这种情况一定是有人在多个地方维护了不一致的换算因子。排查的办法很简单找出所有环对每个环计算累积系数如果偏离 1 超过容差就把环上所有边打印出来人工核对。我写过一个小工具专干这件事上线后帮业务部门捞出来不少脏数据。5.3 缺失单位的兜底策略还有一种常见情况查询的两个单位根本不在同一个连通分量里比如毫升和箱没有任何换算关系。算法题直接返回 -1 或者 None 就行但业务上不能直接抛错否则 BOM 展开到一半就断了。兜底策略一般有几种按基本单位中转很多业务单位都能换算到同一种基本单位比如重量类的都到千克先算 A→基本单位再算基本单位→B两头都能通就解决了。按维度分组把单位分成数量类、重量类、体积类只允许同组转换跨组必须走物料属性。人工维护默认因子实在查不到允许业务人员手动补一条换算率但必须留日志和审批痕迹。我在项目里通常三种都上优先自动按基本单位中转查不到再走分组校验最后才允许人工兜底。5.4 排查思路速查表把上面这些经验整理成一张速查表给你排查的时候对着看现象可能原因处理建议查询返回不可达单位不在同一连通分量 / 反向边没建检查 graph 里是否有两边的入边结果与手工计算差一点浮点累积误差改成高精度运算按阈值比较递归栈溢出图中有环 / 递归过深加 visited换 BFS 或并查集同一个换算出现两个答案输入有矛盾因子做环检测打印环上因子大数据量查询性能差每次查询都 DFS换 Floyd-Warshall 或加权并查集BOM 金额对不上账换算之后舍入方式不统一统一舍入规则记录差异还有一个小技巧排查单位换算问题时别只盯着代码先拿几个典型查询手工算一遍把期望结果写死成测试用例。单位换算这种纯函数逻辑最适合用单元测试锁住行为。我在项目里就是先建立一批厘米转千米箱转千克的基准用例每次改动换算引擎跑一遍回归测试比什么都稳。我个人在实际项目里最大的体会是单位转换这类问题的难点从来不在算法本身而在关系是否可信、精度是否可控、边界是否可兜底。把算法题的思路吃透之后落到真实业务里眼里盯的就不再是 DFS 怎么写而是数据从哪来、错了怎么发现、发现之后怎么恢复。能把这三件事想明白不管是在 LeetCode 上写代码还是在 SAP 里调 BOM你都会顺手很多。