题目

描述

牛客项目发布项目版本时会有版本号，比如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.

方法一

思路

比较版本号，类似于比较ip地址，很容易想到依据“.”进行字符串分割，接着将分割出的字符串转换成整数进行比较。

具体步骤

1.建立两个字符数组，将两个版本号分割成字符串数组存储在建立的两个字符串数组中；
2.遍历数组，比较对应位置的数据大小；
3.若是两个数组长度不同，且一个数组遍历完后，均是相等，则继续遍历剩下的数组。

代码如下：

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

   int i = 0;
   // 遍历数组，比较相应位置的大小
   for (; i < numStr1.length; ++i){
       int num1 = Integer.valueOf(numStr1[i]);
       if (i >= numStr2.length){
           break;
       }
       int num2 = Integer.valueOf(numStr2[i]);
       if (num2 < num1){
           return 1;
       }
       if (num2 > num1){
           return -1;
       }
   }
   // str2多的部分是否为0，不为0，则version2大
   if ( i < numStr2.length){
       while(i < numStr2.length){
           if (Integer.valueOf(numStr2[i]) != 0){
               return -1;
           }
           ++i;
       }
   }
   // str1多的部分是否为0，不为0，则version1大
   if (i < numStr1.length){
       while(i < numStr1.length){
           if (Integer.valueOf(numStr1[i]) != 0){
               return 1;
           }
           ++i;
       }
   }
   // 相等
   return 0;
}
}

时间复杂度： $O(max\left\{m,n\right\})$ ，遍历两个字符串，所以时间复杂度为其中最大的；
空间复杂度： $O(m+n)$ ，存储两个version版本。

方法二

思路
由于方法一需要额外的辅助空间来辅助计算，所以考虑使用双指针，在遍历版本号字符串时，直接进行数据大小的比较，即边分割边比较。“abc”转换成整数的公式是：a*100+b*10+c,所以在指针行进过程中，只需将原数乘以10+新遍历的数即可。

具体步骤
参考下图的例子：
代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // 双指针
        int index1 = 0;
        int index2 = 0;
        // 循环遍历
        while(index1 < version1.length() 
              || index2 < version2.length()){
            int num1 = 0;
            int num2 = 0;
            // 依据"."进行分割
            while (index1 < version1.length() && 
                   version1.charAt(index1) != '.'){
                num1 = num1*10 + (version1.charAt(index1++) - '0');
            }
            // 依据"."进行分割
            while (index2 < version2.length() && 
                   version2.charAt(index2) != '.'){
                num2 = num2*10 + (version2.charAt(index2++) - '0');
            }
            if (num1 < num2){
                return -1;
            }
            if (num1 > num2){
                return 1; 
            }
            ++index1;
            ++index2;
        }

        // 相等
        return 0;
    }
}

时间复杂度： $O(max\left\{m,n\right\})$ ，遍历两个字符串，所以时间复杂度为其中最大的；
空间复杂度： $O(1)$ 常数级空间复杂度。

题解 | #比较版本号#

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤