首页 > 试题广场 >

比较版本号

[编程题]比较版本号

热度指数：99809 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛客项目发布项目版本时会有版本号，比如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(1)$ ，时间复杂度 $O(n)$

示例1

输入

"1.1","2.1"

输出

-1

说明

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

示例2

输入

"1.1","1.01"

输出

说明

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"

输出

说明

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

示例5

输入

"0.226","0.36"

输出

说明

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

算法知识视频讲解

C++

『待‐无期』

O(1)空间，O（n）时间复杂度。

class Solution {
public:
    int compare(string version1, string version2) {
        // write code here
        version1.push_back('.');
        version2.push_back('.');
        int l1=0,r1=0,l2=0,r2=0;
        while(r1<version1.size()&&r2<version2.size()){
            if(version1[r1]!='.')r1++;
            if(version2[r2]!='.')r2++;
            if(version2[r2]=='.'&&version1[r1]=='.'){
                while(version1[l1]=='0')
                    l1++;
                while(version2[l2]=='0')
                    l2++;
                if(r1-l1>r2-l2)return 1;
                else if(r1-l1<r2-l2)return -1;
                else {
                    while(version1[l1]!='.'){
                        if(version1[l1]>version2[l2])
                            return 1;
                        else if(version1[l1]<version2[l2])
                            return -1;
                        l1++;
                        l2++;
                    }
                    r2++;
                    r1++;
                    l1=r1;
                    l2=r2;
                }
            }
        }
        while(r1<version1.size()){
            if(version1[r1]!='0'&&version1[r1]!='.'){
                return 1;
            }
            r1++;
        }
        while(r2<version2.size()){
            if(version2[r2]!='0'&&version2[r2]!='.'){
                return -1;
            }
            r2++;
        }
        return 0;
    }
};

发表于 2021-11-08 16:28:40 回复(0)

Java

勇敢牛牛，不怕困难！

import java.util.*;
import java.math.BigInteger;

public class Solution {
  public int compare(String version1, String version2) {
    String[] v1 = version1.split("\\.");
    String[] v2 = version2.split("\\.");
    for (int i = 0; i < Math.max(v1.length, v2.length); ++i) { // Revision 修订号
      BigInteger rev1 = i < v1.length ? new BigInteger(v1[i]) : new BigInteger("0");
      BigInteger rev2 = i < v2.length ? new BigInteger(v2[i]) : new BigInteger("0");;
      if (rev1.compareTo(rev2) < 0) return -1;
      if (rev1.compareTo(rev2) > 0) return 1;
    }
    return 0;
  }
}

发表于 2021-08-15 14:50:12 回复(0)

Java

阿尼亚瓦库瓦库

import java.util.*;


public class Solution {
    
    public int compare (String version1, String version2) {
        // write code here
        String[] numsOfV1 = version1.split("\\."); // 记得这里分割的时候需要加两个斜杠
        String[] numsOfV2 = version2.split("\\.");
        
        int index = 0;
        
        while (index < numsOfV1.length && index < numsOfV2.length) {
            int num1 = Integer.parseInt(numsOfV1[index]);
            int num2 = Integer.parseInt(numsOfV2[index]);
            if (num1 > num2) {
                return 1;
            } else if (num1 < num2) {
                return -1;
            }
            index ++;
        }
        
        while (index < numsOfV1.length) {
            int num1 = Integer.parseInt(numsOfV1[index]);
            if (num1 > 0) {
                return 1;
            }
            index ++;
        }
        
        while (index < numsOfV2.length) {
            int num2 = Integer.parseInt(numsOfV2[index]);
            if (num2 > 0) {
                return -1;
            }
            index ++;
        }
        
        return 0;
    }
}

发表于 2021-05-15 14:30:18 回复(0)

C++

等一个广哥哥

class Solution {
public:
int compare(string version1, string version2) {
//双指针
int n1 = version1.size();
int n2 = version2.size();
int cur1 = 0,cur2 = 0;
while(cur1 < n1 || cur2 < n2)
{
int num1 = 0,num2 = 0;
while(cur1 < n1 && version1[cur1] != '.')
{
num1 = num1 * 10 + version1[cur1] - '0';
cur1++;
}
while(cur2 < n2 && version2[cur2] != '.')
{
num2 = num2 * 10 + version2[cur2] - '0';
cur2++;
}
if(num1 < num2)
return -1;
if(num1 > num2)
return 1;
cur1++;
cur2++;
}
return 0;
}
};

发表于 2021-08-20 19:40:13 回复(0)

取nm名字全被取了

int compare(char* version1, char* version2 ) 
{
    int num1=0,num2=0;
    while(*version1 != 0 || *version2 != 0)
    {
        while(*version1 != '.' && *version1 != 0)
        {
            num1 = num1*10+*version1 - '0';
            version1++;
        }
        while(*version2 != '.' && *version2 != 0)
        {
            num2 = num2*10+*version2 - '0';
            version2++;
        }
        if(num1 > num2)
        {
            return 1;
        }
        else if(num1 < num2)
        {
            return -1;
        }
        if(*version1 != 0)
        version1++;
        if(*version2 != 0)
        version2++;
        num1 = 0;
        num2 = 0;
    }
    return 0;
    // write code here
}

发表于 2022-11-05 17:03:36 回复(1)

C++

木析

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    int compare(string version1, string version2) {
        int len1=version1.size(), len2=version2.size();
        int i=0, j=0;
        while(i<len1 || j<len2) {
            long x=0; //题目说版本号的每一节可能超过int范围，所以用long
            long y=0;
            while(i<len1 && version1[i]!='.') {
                x=x*10+(version1[i]-'0');
                ++i;
            }
            ++i; //跳过.
            while(j<len2 && version2[j]!='.') {
                y=y*10+(version2[j]-'0');
                ++j;
            }
            ++j;
            if(x>y) {
                return 1;
            }else if(x<y)
                return -1;
        }
        return 0;
    }
};

发表于 2021-09-17 21:13:24 回复(1)

Java

七r

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // write code here
        //第一个为版本号，先对比版本号
        //后面的为修订号，如果有前导0忽略掉，如果后面没有0默认为0
        String[] ver1 = version1.split("\\.");
        String[] ver2 = version2.split("\\.");
        int len = Math.max(ver1.length,ver2.length);
        for(int i = 0;i<len;i++){
            int t1 = i<ver1.length?Integer.parseInt(ver1[i]):0;
            int t2 = i<ver2.length?Integer.parseInt(ver2[i]):0;
            if(t1 > t2) return 1;
            else if(t1 < t2) return -1;
        }
        return 0;
    }
}

发表于 2022-08-12 10:36:14 回复(1)

Java

键盘都敲坏了.

双指针查找，具体思路如下

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // write code here
        int i = 0, j = 0; // i是version1指针，j是version2指针
        // sum1存储version1中根据小数点分组的每一组版本之和，
        // sum2存储version2中根据小数点分组的每一组版本之和
        long sum1,sum2;

        // 由题得知:
        //          如果版本号没有指定某个下标处的修订号，则该修订号视为0。
        //          例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
        // 所以 i或j 其中一个符合条件则while继续。 （假设i下标已经越界，那么sum1的版本就是0，不会再继续从version1中获取版本号）
        while (i < version1.length() || j < version2.length()){
            // 设置初始值sum1 sum2 都为0
            sum1 = 0; sum2 = 0;
            // 只要i不越界，并且没有匹配到小数点时 一直内循环查找version1 , 这里的小数点判断实际上是将版本号根据小数点进行分组，每一组进行比较
            while (i < version1.length() && ! ".".equals(version1.substring(i, i + 1))){
                // sum1 * 10的原因是将上次结果的位数进一，然后再加上本次的数
                sum1 = sum1 * 10 + Long.parseLong(version1.substring(i, i + 1)) ;
                ++i; // 指针后移
            }
            // 当退出循环时，指针继续后移，这里考虑到了while退出的原因是匹配到了小数点，那么这里后移一位，等于跳过小数点，下次大循环会继续从下一段开始
            ++i;

            // 只要j不越界，并且没有匹配到小数点时 一直内循环查找version2 , 这里的小数点判断实际上是将版本号根据小数点进行分组，每一组进行比较
            while (j < version2.length() && ! ".".equals(version2.substring(j, j + 1))){
                // sum2 * 10的原因是将上次结果的位数进一，然后再加上本次的数
                sum2 = sum2 * 10 + Long.parseLong(version2.substring(j, j + 1));
                ++j;// 指针后移
            }
            // 当退出循环时，指针继续后移，这里考虑到了while退出的原因是匹配到了小数点，那么这里后移一位，等于跳过小数点，下次大循环会继续从下一段开始
            ++j;
            
            // 上面两个while退出后，比较当前这一段的版本号大小
            if(sum1 > sum2){
                return 1;
            }else if(sum1 < sum2){
                return -1;
            }
        }
        // 循环没有得到返回时，最终返回0
        return 0;
    
    }
}

发表于 2022-10-31 19:18:21 回复(0)

JavaScript Node

萌萌94

发表于 2022-05-25 17:51:20 回复(0)

Python3

Vivimore

时间复杂度：O(n) 空间复杂度O(1)

class Solution:
    def compare(self , version1: str, version2: str) -> int:
        v1 = list(map(int, version1.split('.')))       
        v2 = list(map(int, version2.split('.')))
        if len(v1) > len(v2):
            v2.extend([0 for i in range(len(v1) - len(v2))])
        elif len(v1) < len(v2):
            v1.extend([0 for i in range(len(v2) - len(v1))])
        for i in range(len(v1)):
            if v1[i] > v2[i]:
                return 1
            elif v1[i] < v2[i]:
                return -1
        return 0

class Solution:
    def compare(self , version1: str, version2: str) -> int:
        n1 = len(version1)
        n2 = len(version2)
        i, j = 0, 0
        while i < n1 or j < n2:
            num1 = 0
            while i < n1 and version1[i] != '.':
                num1 = num1 * 10 + int(version1[i])
                i += 1
            i += 1
            num2 = 0
            while j < n2 and version2[j] != '.':
                num2 = num2 * 10 + int(version2[j])
                j += 1
            j += 1
            if num1 < num2:
                return -1
            elif num1 > num2:
                return 1
        return 0

发表于 2022-05-16 16:24:49 回复(0)

Python 3

lun__

class Solution:
    def compare(self , version1: str, version2: str) -> int:
        # write code here
        fill0 = abs(len(version1) - len(version2))
        if len(version1) < len(version2):
            version1 = version1 + ".0" * fill0
        else:
            version2 = version2 + ".0" * fill0
        l1 = version1.split(".")
        l2 = version2.split(".")
        lmin = min(len(l1), len(l2))
        for i in range(lmin):
            if int(l1[i]) < int(l2[i]): return -1
            if int(l1[i]) > int(l2[i]): return 1
        return 0

发表于 2022-03-24 18:11:28 回复(1)

肉松乳酪夹心

这个代码写得很整洁，思路也很清晰。

感觉这个题目主要考察的点在于split函数对于.圆点的分割要用转义字符。

 String[] str1=version1.split("\\.");
        String[] str2=version2.split("\\.");
        int len1=str1.length;
        int len2=str2.length;

        int max=Math.max(len1,len2);
        for(int i=0;i<max;i++){
            int t1=i<len1?Integer.parseInt(str1[i]):0;
            int t2=i<len2?Integer.parseInt(str2[i]):0;
            if(t1>t2){
                return 1;
            }else if(t2>t1){
                return -1;
            }
        }
        return 0;

发表于 2022-03-24 16:19:06 回复(1)

Java

牛客嗷嗷

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * 
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public int compare(String version1, String version2) {
        // write code here
        String[] s1 = version1.split("\\.");
        String[] s2 = version2.split("\\.");

        double[] a1 = new double[s1.length];
        double[] a2 = new double[s2.length];

        for (int i = 0; i < s1.length; i++)
            a1[i] = Double.parseDouble(s1[i]);

        for (int i = 0; i < s2.length; i++)
            a2[i] = Double.parseDouble(s2[i]);

        int m = s1.length, n = s2.length;

        for (int i = 0; i < Math.min(m, n); i++) {
            if (a1[i] == a2[i])
                continue;
            else if (a1[i] < a2[i])
                return -1;
            else
                return 1;
        }

        if (m < n)
            for (int i = m; i < n; i++)
                if (a2[i] > 0)
                    return -1;

        if (m > n) {
            for (int j = n; j < m; j++)
                if (a1[j] > 0)
                    return 1;
        }

        return 0;
    }

}

发表于 2022-03-04 20:34:24 回复(0)

Java

莫里Mori

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // write code here
        String[] s1 = version1.split("\\.");
        String[] s2 = version2.split("\\.");
        int i = 0, j = 0;
        while(i < s1.length || j < s2.length){
            // 只有s2有版本号
            if(i >= s1.length){
                int p = 0;
                // 去除前导0
                while(p < s2[j].length() && s2[j].charAt(p) == '0'){
                    p ++;
                }
                if(p < s2[j].length()){
                    return -1;
                }
            }
            // 只有s1有版本号
            else if(j >= s2.length){
                int p = 0;
                // 去除前导0
                while(p < s1[i].length() && s1[i].charAt(p) == '0'){
                    p ++;
                }
                if(p < s1[i].length()){
                    return 1;
                }
            }
            // s1和s2都有版本号
            else{
                int p1 = 0, p2 = 0;
                // 去除前导0
                while(p1 < s1[i].length() && s1[i].charAt(p1) == '0'){
                    p1 ++;
                }
                // 去除前导0
                while(p2 < s2[j].length() && s2[j].charAt(p2) == '0'){
                    p2 ++;
                }
                if(s1[i].length() - p1 != s2[j].length() - p2){
                    return s1[i].length() - p1 > s2[j].length() - p2? 1: -1;
                }
                while(p1 < s1[i].length()){
                    if(s1[i].charAt(p1) != s2[j].charAt(p2)){
                        return s1[i].charAt(p1) > s2[j].charAt(p2)? 1: -1;
                    }
                    p1 ++;
                    p2 ++;
                }
            }
            i ++;
            j ++;
        }
        return 0;
    }
}

发表于 2021-08-09 11:26:18 回复(0)

Python 3

慵懒的大圣

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 比较版本号
# @param version1 string字符串 
# @param version2 string字符串 
# @return int整型
#
class Solution:
    def compare(self , version1 , version2 ):
        # write code here
        vec1 = version1.split('.')
        vec2 = version2.split('.')
        
        if len(vec1) == 0 or len(vec2) == 0:
            return None
        
        if len(vec1) < len(vec2):
            while len(vec1) < len(vec2):
                vec1 = vec1 + ['0']
        elif len(vec1) > len(vec2):
            while len(vec1) > len(vec2):
                vec2 = vec2 + ['0']
        
        i = 0
        while i < len(vec1):
            if int(vec1[i]) == int(vec2[i]):
                i = i + 1
            elif int(vec1[i]) > int(vec2[i]):
                return 1
            else:
                return -1
        
        return 0

编辑于 2021-07-16 11:00:03 回复(1)

肥猿

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // write code here
        String[] str1=version1.split("\\.");
        String[] str2=version2.split("\\.");
        int i=0;
        for(;i<Math.min(str1.length,str2.length);i++){
            if(Integer.parseInt(str1[i])==Integer.parseInt(str2[i])) continue;
            return Integer.parseInt(str1[i])>Integer.parseInt(str2[i])?1:-1;
        }
        while(i<str1.length){
            if(Integer.parseInt(str1[i])>0) return 1;
            i++;
        }
        while(i<str2.length){
            if(Integer.parseInt(str2[i])>0) return -1;
            i++;
        }
        return 0;
    }
}

发表于 2021-03-20 16:29:02 回复(1)

Python3

可道非常道

class Solution:
    def compare(self , version1: str, version2: str) -> int:
        # write code here
        ver1 = version1.split('.')
        ver2 = version2.split('.')
        n1, n2 = len(ver1), len(ver2)
        
        for i in range(max(n1, n2)):
            num1 = int(ver1[i]) if i < n1 else 0
            num2 = int(ver2[i]) if i < n2 else 0
            
            if num1 > num2:
                return 1
            elif num1 < num2:
                return -1
        
        return 0

发表于 2023-10-16 09:53:26 回复(0)

FFTang

import itertools
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 比较版本号
# @param version1 string字符串 
# @param version2 string字符串 
# @return int整型
#
class Solution:
    def compare(self , version1: str, version2: str) -> int:
        # write code here
        list1 = map(int, version1.split('.'))
        list2 = map(int, version2.split('.'))
        for i,j in itertools.zip_longest(list1, list2, fillvalue = 0):
            if i < j:
                return -1
            elif i > j:
                return 1
            else:
                continue 
        return 0

发表于 2023-09-05 15:06:28 回复(0)

小刘新鲜事儿

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */


    public int compare(String version1, String version2) {
        List<Integer> list1 = Arrays.stream(version1.split("\\."))
                .mapToInt(data -> Integer.parseInt(data))
                .boxed()
                .collect(Collectors.toList());
     
        List<Integer> list2 = Arrays.stream(version2.split("\\."))
                .mapToInt(data -> Integer.parseInt(data))
                .boxed()
                .collect(Collectors.toList());
     

        Iterator<Integer> iterList1 = list1.iterator();
        Iterator<Integer> iterList2 = list2.iterator();

        while (iterList1.hasNext() && iterList2.hasNext()) {
            int value1 = iterList1.next().intValue();
            int value2 = iterList2.next().intValue();
            if (value1 < value2) {
                return -1;
            } else if (value1 > value2) {
                return 1;
            }
        }

        while (iterList1.hasNext()) {
            if (iterList1.next().intValue() > 0) {
                return 1;
            }
        }

        while (iterList2.hasNext()) {
            if (iterList2.next().intValue() > 0) {
                return -1;
            }
        }

        return 0;
    }
}

发表于 2023-05-08 11:35:09 回复(1)

为你扣下F键

package main

func compare(version1 string, version2 string) int {
	m, n := len(version1), len(version2)
	i, j := 0, 0
	for i < m || j < n {
		var a, b int
		for i < m && version1[i] != '.' {
			a = a*10 + int(version1[i]-'0')
			i++
		}
		for j < n && version2[j] != '.' {
			b = b*10 + int(version2[j]-'0')
			j++
		}
		if a > b {
			return 1
		} else if a < b {
			return -1
		}
		i++
		j++
	}
	return 0
}

发表于 2023-02-19 20:46:42 回复(0)

提交观点

问题信息

字符串双指针

上传者：牛客332641号

难度：

192条回答 552收藏 11641浏览

通过挑战的用户

查看代码

牛客30838...

2022-12-25 14:26:49
半日深愛

2022-11-29 17:57:02
闻小屿

2022-11-12 11:21:27
神秘巨星1

2022-11-04 17:05:29
金刀伏特加

2022-10-14 08:58:39

比较版本号

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题