156. Compare Version Numbers

题目

给定两个版本号，比较这两个版本号大小，如果 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