题目
给定两个版本号,比较这两个版本号大小,如果 v1 > v2 返回 1,如果 v1 < v2 返回 -1 ,其他情况返回 0。
解析
这是一个工程性的问题,要比较两个版本号,是数字比较大小,这就需要将版本号转换成数组。然后比较两个数组的大小。
这里需要两个函数
compare([]int, []int)
convert(string) []int
为了将字符串转换成数组,首先需要根据 . 分割成字符串组
split(string, char) []string
分割成字符串组之后,需要将每一个字符串格式化为没有前导 0 的数字
format(string) int
所以一共需要实现四个函数。
伪代码
split(s, char) []string
split 的关键在于找到分割符号时,确定前后界,并且当最后一次循环结束时,可能并没有找到分离符号,此时也需要将最后一个子串作为结果一部分
i=0
j=0
for ;j < len(s); j++
if s[j] == char
rst+=s[i:j]
i=j+1
if i<len(s)
rst+=s[i:j]
foramt(s) int
格式化的关键在于先忽略前导0,然后计算后边的值
i=0
for i<len(s) && s[i] == '0'; i++
{}
for i<len(s)
rst=rst*10+s[i]-'0'
compare(v1, v2) int
比较首先要处理长度不一致的情况,假设 v1 比 v2 长,不然的话,交换 v1, v2。用一个标志 swap
来标记是否交换。
此时得到一个 v1 和 v2。
处理长度不同的情况,首先比较长度相同的部分,如果长度相同的部分比较出了大小,直接返回。
然后检索更长的那个数组剩余部分是否有 >=1 的情况,如果有,返回,如果没有,说明两个版本相同返回 0。
在返回结果时,我们假设了 len(v1) >= len(v2),所以对于结果,要参考 swap
标志进行转换。
if len(v1) < len(v2)
v1,v2 = v2, v1
swap = true
for i=0;i<len(v2);i++
if v1[i] = v2[i]
continue
if v1[i] > v2[i]
return 1, swap
if v1[i] < v2[i]
return -1, swap
for i=len(v2); i<len(v1);i++
if v1[i] >=1
return 1, swap
return 0
代码
func compareVersion(version1 string, version2 string) int {
return compare(convert(version1), convert(version2))
}
func convert(version string) []int {
vs := split(version, '.')
rst := make([]int, len(vs))
for i := range vs {
rst[i] = format(vs[i])
}
return rst
}
func split(str string, char byte) []string{
var rst []string
bs:=[]byte(str)
i:=0
j:=0
for j < len(bs) {
if bs[j] == char {
rst=append(rst, string(bs[i:j]))
i=j+1
}
j++
}
if i<len(bs) {
rst = append(rst, string(bs[i:j]))
}
return rst
}
func format(ver string) int {
i:=0
for ;i<len(ver) && ver[i] == '0'; i++ {
}
rst:=0
for i<len(ver) {
rst = rst*10 + int(ver[i]-'0')
i++
}
return rst
}
// 假设 version1 比 version2 长
func compare(version1 []int, version2 []int) int {
swap:=false
if len(version1) < len(version2) {
version1, version2 = version2, version1
swap = true
}
for i:=0;i<len(version2);i++ {
if version1[i] == version2[i] {
continue
}
if version1[i] > version2[i] {
return rst(1, swap)
}
if version1[i] < version2[i] {
return rst(-1, swap)
}
}
for i:=len(version2); i<len(version1); i++ {
if version1[i] >= 1 {
return rst(1, swap)
}
}
return 0
}
func rst(flag int, swap bool) int {
if swap {
return ^flag+1
}
return flag
}
image.png
网友评论