当前位置：首页 > ops >正文

可视化图解算法45：比较版本号

ops 2025/7/27 23:42:25

1. 题目

牛客网面试笔试 TOP101 | LeetCode 165. 比较版本号

描述

软件项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等

现在给你2个版本号version1和version2，请你比较他们的大小

版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号

每个版本号至少包含1个修订号。

修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。

比较规则：

一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的

二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1

三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

数据范围：

1 <= version1.length, version2.length <= 1000

version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围

进阶：时间复杂度 O(n)

示例1

输入：

"1.1","2.1"

返回值：

-1

说明：

version1 中下标为 0 的修订号是 "1"，version2 中下标为 0 的修订号是 "2" 。1 < 2，所以 version1 < version2，返回-1

示例2

输入：

"1.1","1.01"

返回值：

0

说明：

version2忽略前导0，为"1.1"，和version相同，返回0

示例3

输入：

"1.1","1.1.1"

返回值：

-1

说明：

"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1，所以version1 < version2，返回-1

示例4

输入：

"2.0.1","2"

返回值：

1

说明：

version1的下标2>version2的下标2，返回1

示例5

输入：

"0.226","0.36"

返回值：

1

说明：

226>36，version1的下标2>version2的下标2，返回1

2. 解题思路

版本号的比较有两种方法：

方法1：对字符串按照" . "进行切割，组成新的数组，再对两个数组逐块进行比较
方法2：双指针法，时间复杂度、空间复杂度都有所减少。

指针1指向第一个字符串，指针2指向第二个字符串。对每一块（“ . ”间隔）的内容转换成int进行比较。

方法1相对来说比较简单，我们重点讲解方法2实现版本号的比较。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372591
Java版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367847
Golang版本：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364845

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 比较版本号* @param version1 string字符串* @param version2 string字符串* @return int整型*/
func compare(version1 string, version2 string) int {// write code here// 1. 定义变量i := 0j := 0// 2. 通过循环比较版本值的大小for i < len(version1) || j < len(version2) {//2.1 每一组修订号：字符 转 intnum1 := 0num2 := 0// version1的修订号（ '.'之前的数字）转换为intfor i < len(version1) && version1[i] != '.' {num1 = num1*10 + int(version1[i]-'0') // version1的修订号（ '.'之前的数字）转换为inti++}// version2 的修订号（ '.'之前的数字）转换为intfor j < len(version2) && version2[j] != '.' {num2 = num2*10 + int(version2[j]-'0')j++}//2.2 修订号进行比较if num1 > num2 {return 1} else if num1 < num2 {return -1} else { //相等，变量后移，继续进行下一组的比较。每一组通过”.“进行分割i++j++}}//3. 所有比较完，说明相等return 0
}

具体完整代码你可以参考下面视频的详细讲解。

Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372591
Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367847
Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364845