比较版本号
P5499. 比较版本号
场次:2026年10月20日-AI方向 · 来源:CodeFun2000 P5499
题目描述
给你两个版本号字符串 和 ,请你比较它们。版本号由一个或多个修订号组成,各修订号由 . 连接。每个修订号由多位数字组成,可能包含前导零。比较修订号时,仅比较忽略前导零后的整数值。如果版本号没有指定某个下标处的修订号,则该修订号视为 。
返回规则: 返回 , 返回 ,相等返回 。
输入格式
第一行输入版本号字符串 ()。
第二行输入版本号字符串 ()。
版本号仅包含数字和 .。
输出格式
输出 1、-1 或 0。
示例
示例 1
输入:
1.2
1.10输出:
-1说明:
第二个修订号 ,所以 。
示例 2
输入:
1.01
1.001输出:
0说明:
忽略前导零,,两个版本号相等。
解题思路
比较语义里藏着两个「隐形」的相等
这题看起来只是把点切开来比大小,真正的判定点却有两处容易漏掉。
第一处是前导零:01 与 001 都是 1,字符串却不相等。第二处是缺省段:1.0.1 与 1,右边只有一段,若只比较两段共有的部分,比完第 0 段就收工,会把两个不等的版本号判成相等。这两条都不是边角情况——1.0 与 1 在真实的版本号里随处可见。
题面的规则可以直接落成三步:每段先归一、再比较,长度不够的一侧按 0 补齐。
第一步:剥掉前导零,全零只留一个数位
def normalize(seg):
"""去掉前导零;全是零时保留一个 "0"。"""
i = 0
while i < len(seg) - 1 and seg[i] == '0':
i += 1
return seg[i:]循环条件是 i < len(seg) - 1,所以要停在最后一位之前:"000" 会被剥成 "0" 而不是空串。归一后的段有两种样子——要么是单个 "0",要么首位不是 0。
第二步:先比位数,位数相同再比字典序
归一之后,段与段之间不能直接比字符串。"10" 与 "9" 按字典序比 "10" < "9"('1' < '9'),但 10 显然比 9 大。十进制里位数多的数一定更大,所以先看长度,长度相同才是同量级的比较,这时字典序与数值序一致:
def cmp_segment(a, b):
"""比较两段修订号:先比有效位数,位数相同再比字典序。"""
a, b = normalize(a), normalize(b)
if len(a) != len(b):
return 1 if len(a) > len(b) else -1
if a == b:
return 0
return 1 if a > b else -1这一步只做字符扫描,全程不构造整数——换到没有大整数类型的语言里也照样能用。
第三步:按较长的段数循环,缺的段按 0 参与比较
def compare_version(v1, v2):
left = v1.split('.')
right = v2.split('.')
# 按较长的段数循环,短的那个版本号后面按 0 补齐
for i in range(max(len(left), len(right))):
a = left[i] if i < len(left) else '0'
b = right[i] if i < len(right) else '0'
diff = cmp_segment(a, b)
if diff != 0:
return diff
return 0循环上界取 max(len(left), len(right)),越界的一侧补 '0',等价于题面「缺少的修订号视为 0」。return diff 写在循环里,第一个不等的段就定下结论;能走出循环说明每一段都相等,此时两串版本号语义相同,返回 0。
要不要干脆转成整数
Python 的整数没有位宽上限, 这点长度 int(seg) 完全跑得动,看起来比上面三段代码都省事。但有两笔代价:
- 把长度 的十进制串转成大整数是 的代价,字符串比较只扫一遍,;
- 换到 C++ / Java,
long long装不下 500 位,还得手写大整数比较。字符串比较这套写法在哪种语言里都是同一份。
所以下面全程只做「数位数 + 比字典序」,一次整数转换都不做。
完整代码实现
import sys
def normalize(seg):
"""去掉前导零;全是零时保留一个 "0"。"""
i = 0
while i < len(seg) - 1 and seg[i] == '0':
i += 1
return seg[i:]
def cmp_segment(a, b):
"""比较两段修订号:先比有效位数,位数相同再比字典序。"""
a, b = normalize(a), normalize(b)
if len(a) != len(b):
return 1 if len(a) > len(b) else -1
if a == b:
return 0
return 1 if a > b else -1
def compare_version(v1, v2):
left = v1.split('.')
right = v2.split('.')
# 按较长的段数循环,短的那个版本号后面按 0 补齐
for i in range(max(len(left), len(right))):
a = left[i] if i < len(left) else '0'
b = right[i] if i < len(right) else '0'
diff = cmp_segment(a, b)
if diff != 0:
return diff
return 0
def solve():
# 两个版本号可能分两行,也可能用空格隔开,按空白切分都能读
tokens = sys.stdin.read().split()
if len(tokens) < 2:
return
print(compare_version(tokens[0], tokens[1]))
if __name__ == "__main__":
solve()示例推演
示例 1:1.2 与 1.10
切分:["1", "2"] 与 ["1", "10"],两侧都是 2 段,循环 2 轮。
| 轮次 | 左段 | 归一后 | 右段 | 归一后 | 长度比较 | 结果 |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 = 1,内容相同 | 0 |
| 1 | 2 | 2 | 10 | 10 | 1 < 2 | -1 |
第 1 轮长度就已分出胜负,返回 -1。这一轮正是 cmp_segment 里 len(a) != len(b) 那一段在起作用:若跳过长度直接比字符串,'2' > '1' 会给出 1,结论正好反了。
示例 2:1.01 与 1.001
切分:["1", "01"] 与 ["1", "001"],两侧都是 2 段。
| 轮次 | 左段 | 归一后 | 右段 | 归一后 | 长度比较 | 结果 |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 = 1,内容相同 | 0 |
| 1 | 01 | 1 | 001 | 1 | 1 = 1,内容相同 | 0 |
两轮都是 0,走出循环,返回 0。前导零在这里被完全吃掉,01 与 001 落成同一个 "1"。归一必须发生在长度比较之前:拿原始段比长度,"01"(2 位)与 "001"(3 位)会得出 1,把相等判成大于。
段数不同时:1.0.1 与 1
两组样例的段数都相同,缺省段这条规则要单独走一遍。切分后是 ["1", "0", "1"] 与 ["1"],上界取 ,右侧第 1、2 段越界,各补一个 '0'。
| 轮次 | 左段 | 右段 | 归一后 | 结果 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 / 1 | 0 |
| 1 | 0 | 缺省补 0 | 0 / 0 | 0 |
| 2 | 1 | 缺省补 0 | 1 / 0 | 长度相同,'1' > '0',返回 1 |
第 2 轮即返回 1,输出 1。若在这里改用 min(len(left), len(right)) 作上界,只比第 0 段就会返回 0,把 1.0.1 判成与 1 相等。
复杂度分析
记两个版本号的总长度(字符数)。
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
每段转成 int 再比 | 十进制串转大整数是二次代价;C++ / Java 里 500 位还得自己实现大整数 | ||
| 归一后按位数 + 字典序逐段比较(最优) | 每段只扫一遍字符,全程不构造整数 |
空间里的 来自 split('.') 切出的段列表;比较本身只用两个下标。两个版本号段数不同时,补齐的 '0' 是常量串,不额外占空间。
易错点总结
1. 省掉长度比较,直接按字符串比
cmp_segment 里只写 return 1 if a > b else -1(去掉 len(a) != len(b) 那一段),归一后的段依然没有前导零,看上去「字符串序 = 数值序」,但对位数不同的两段就错了:'10' < '9'。输入 1.10 / 1.9 会输出 -1,正确答案是 1。位数不同必须先由长度定胜负。
2. 循环上界用 min 而不是 max
compare_version 里把 range(max(len(left), len(right))) 写成 range(min(...)),缺省段就永远不参与比较。输入 1.0.1 / 1 时只比第 0 段就走出循环,返回 0——两个语义不同的版本号被判成相等,而这段代码在段数相同的输入上一切正常,很难在自测里发现。上界留对了却不写 if i < len(left) 的兜底,同一个输入会直接抛 IndexError: list index out of range。
扩展思考
- 语义化版本号(semver):真实世界的版本号还会带字母,
1.2.0-alpha.1。这时段与段之间不再是纯数字比较:数字段按数值、字母段按字典序,且规范约定预发布段的优先级低于对应的正式版本。比较框架没变——仍然是切段、逐段比、遇到不等即返回——只是「一段怎么比」从「长度 + 字典序」换成了 semver 自己的规则表。 - 一次比较多个版本号:若要把 个版本号排序,逐对比较是 ;把每个修订号归一成字符串键、按段组成元组后直接排序,比较次数一样但每次比较交给语言自带的元组比较,常数小得多。