美文网首页
156. Compare Version Numbers

156. Compare Version Numbers

作者: sarto | 来源:发表于2022-09-22 10:05 被阅读0次

    题目

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

    相关文章

      网友评论

          本文标题:156. Compare Version Numbers

          本文链接:https://www.haomeiwen.com/subject/zfzgortx.html