Massive Algorithms: LeetCode 165 - Compare Version Numbers

LeetCode 165 - Compare Version Numbers

[leetcode] Compare Version Numbers - 追梦船的专栏 - 博客频道 - CSDN.NET
Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

从高位到低位递归解决。注意特殊case （1,1.0）;

X. Constant Space
http://www.jyuan92.com/blog/leetcode-compare-version-numbers/
https://leetcode.com/problems/compare-version-numbers/discuss/50788/My-JAVA-solution-without-split
https://leetcode.com/problems/compare-version-numbers/discuss/50767/My-2ms-easy-solution-with-CC%2B%2B

Rather than use two String[], we can handle this in constant space.

public int compareVersion2(String version1, String version2) {

   if (null == version1 || null == version2) {

       return 0;

}

   if (version1.equals(version2)) {

       return 0;

}

   int aLength = version1.length();

   int bLength = version2.length();

   int i = 0;

   int j = 0;

   while (i < aLength || j < bLength) {

       int aTemp = 0;

       int bTemp = 0;

       while (i < aLength && version1.charAt(i) != '.') {

           aTemp  = aTemp * 10 + version1.charAt(i) - '0';

           i++;

}

       while (j < bLength && version2.charAt(j) != '.') {

           bTemp  = bTemp * 10 + version2.charAt(j) - '0';

           j++;

}

       if (aTemp < bTemp) {

           return -1;

}

       if (aTemp > bTemp) {

           return 1;

}

       i++;

       j++;

}

   return 0;

}

https://leetcode.com/discuss/20675/solution-using-two-pointer-java

Keep two pointer to get the substring until next "." or the end. Then compare the substring parsed. If one string is ended, assign 0 value for comparing.

public int compareVersion(String version1, String version2) { int i = 0,j = 0; int pre1 = i, pre2 = j; while(i < version1.length() || j < version2.length()){ while(i < version1.length()){ if(version1.charAt(i)=='.') break; i++; } while(j < version2.length()){ if(version2.charAt(j)=='.') break; j++; } int int1 = pre1 < i?Integer.parseInt(version1.substring(pre1,i)):0; int int2 = pre2 < j?Integer.parseInt(version2.substring(pre2,j)):0; if(int1 > int2) return 1; else if(int1 < int2) return -1; pre1 = ++i; pre2 = ++j; } return 0; }
X>
https://leetcode.com/problems/compare-version-numbers/discuss/50774/Accepted-small-Java-solution.

This code assumes that next level is zero if no mo levels in shorter version number. And than compare levels.

public int compareVersion(String version1, String version2) {
    String[] levels1 = version1.split("\\.");
    String[] levels2 = version2.split("\\.");
    
    int length = Math.max(levels1.length, levels2.length);
    for (int i=0; i<length; i++) {
     Integer v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
     Integer v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
     int compare = v1.compareTo(v2);
     if (compare != 0) {
      return compare;
     }
    }
    
    return 0;
}

https://segmentfault.com/a/1190000003803133

1.0和1是一个版本，意味即使长度不一样，也要检查后面是否都是0
1.15要大于1.5，因为前者是第15个子版本，而后者是第5个

最简单的方法就是用split方法按照.分割，然后比对相应的每一个子串。

因为split方法输入的是一个正则表达式所以不能直接用.，而是要用\.，而java的\要转义，所有要用\\.

    public int compareVersion(String version1, String version2) {
        // 按照.进行分割
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int i = 0;
        // 比对相应的子串
        for(; i < v1.length && i < v2.length; i++){
            int val1 = Integer.parseInt(v1[i]);
            int val2 = Integer.parseInt(v2[i]);
            if(val1 < val2) return -1;
            if(val1 > val2) return 1;
        }
        // 如果某个版本号更长，判断其多余部分是否是0，如果不是0，则较长的较大，否则是一样的。
        if(v2.length > v1.length){
            for(; i < v2.length; i++){
                int val = Integer.parseInt(v2[i]);
                if(val != 0) return -1;
            }
        } else if(v1.length > v2.length){
            for(; i < v1.length; i++){
                int val = Integer.parseInt(v1[i]);
                if(val != 0) return 1;
            }
        }
        return 0;
    }

http://yuanhsh.iteye.com/blog/2175676

注意各种edge case，比如：0.0.1, 0.1 和 1.0, 1

public int compareVersion(String version1, String version2) {
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
int maxLength = Math.max(v1.length, v2.length);
for(int i=0; i<maxLength; i++) {
Integer a = i<v1.length ? Integer.parseInt(v1[i]) : 0;
Integer b = i<v2.length ? Integer.parseInt(v2[i]) : 0;
int res = a.compareTo(b);
if(res != 0) return res;
}
return 0;
}

http://www.programcreek.com/2014/03/leetcode-compare-version-numbers-java/

public int compareVersion(String version1, String version2) {
    String[] arr1 = version1.split("\\.");
    String[] arr2 = version2.split("\\.");
 
    int i=0;
    while(i<arr1.length || i<arr2.length){
        if(i<arr1.length && i<arr2.length){
            if(Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])){
                return -1;
            }else if(Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])){
                return 1;
            }
        } else if(i<arr1.length){
            if(Integer.parseInt(arr1[i]) != 0){
                return 1;
            }
        } else if(i<arr2.length){
           if(Integer.parseInt(arr2[i]) != 0){
                return -1;
            }
        }
 
        i++;
    }
 
    return 0;
}

http://www.zhuangjingyang.com/leetcode-compare-version-numbers/

   public  int compareVersion(String version1, String version2) {

     String[] v1 = version1.split("\\.");

     String[] v2 = version2.split("\\.");

     int i=0;

     for(;i<v1.length && i < v2.length;i++){

      int t  = compare(v1[i],v2[i]);

      if(t != 0)

       return t;

}

     //if version1 is longer

     while(i<v1.length){

      if(Integer.parseInt(v1[i++])!=0)

       return 1;

}

     //if version2 is longer

     while(i<v2.length){

      if(Integer.parseInt(v2[i++])!=0)

       return -1;

}

     return 0;

}

    public  int compare(String t1,String t2){

     int v1 = Integer.parseInt(t1);

     int v2 = Integer.parseInt(t2);

     return v1>v2?1:v1<v2?-1:0;

}

public int compareVersion(String version1, String version2) { //java
if(version1.equals(version2))
return 0;
int fversion1 , fversion2;
String sversion1,sversion2;
if(version1.contains(".")){
int pos = version1.indexOf(".");
fversion1 = Integer.valueOf(version1.substring(0,pos));
sversion1 = version1.substring(pos+1,version1.length());
}
else {
fversion1 = Integer.valueOf(version1);
sversion1 = "0";
}
if(version2.contains(".")){
int pos = version2.indexOf(".");
fversion2 = Integer.valueOf(version2.substring(0,pos));
sversion2 = version2.substring(pos+1,version2.length());
}
else {
fversion2 = Integer.valueOf(version2);
sversion2 = "0";
}
if(fversion1 > fversion2)
return 1;
else if(fversion1 < fversion2)
return -1;
else return compareVersion(sversion1, sversion2);
}

http://blog.csdn.net/lavorange/article/details/42048687
算法思路：1.首先考虑将两个字符串version1和version2进行切分，因为可能会出现这样的测试用例"1.0.1"，有多个点。

2.将按照"."分割之后的数字放到一个容器vector里面或者一个数组里面就行了。

3.然后依次进行比较。有一点需要注意的是，有类似的用例"1.0.0"和"1"其实是相等的，因此，要将容器或者数组中的后缀0去掉，那么比较的时候就没有什么顾虑了。

void split_string(const char *str , vector<int> &v)
{
char *buf = new char[ strlen(str) + 1 ];
strcpy(buf,str);
char *p = strtok(buf,".");
while( p!=NULL )
{
v.push_back( atoi(p) ) ;
p = strtok(NULL,".");
}
}
//compare two version
int compareVersion(string version1, string version2)
{
const char *str1 = version1.c_str();
const char *str2 = version2.c_str();
split_string(str1,v1);
split_string(str2,v2);
return judge();
}
int judge()
{
//prune the suffix zero : 1.0 == 1
while( v1.size()!=0 && v1[v1.size()-1]==0 )
{
v1.pop_back();
}
while( v2.size()!=0 && v2[v2.size()-1]==0 )
{
v2.pop_back();
}
int size = min( v1.size(),v2.size() );
int i;
for(i=0;i<size;i++)
{
if( v1[i]>v2[i] ) return 1;
else if( v1[i]<v2[i] ) return -1;
else continue;
}
if( v1.size() > v2.size() )
{
return 1;
}
else if( v1.size() < v2.size() ) return -1;
else return 0;
}
};

https://leetcode.com/discuss/24078/simple-java-solution
What if the value of a subversion is larger than Integer. MAX_VALUE?

Some guys point to MAX_VALUE problem, I think it is a good point. I revise my solution to solve this problem and without using compareTo().

The basic idea is same.

strCmp() method is used to compare two tokens without parsing to int. The idea of this method is very very similar: fill zeros if the length is not consistent.

for example: "001" vs. "1" --> "001" vs. "001"

public int compareVersion(String version1, String version2) { String ver1[] = version1.split("\\."); String ver2[] = version2.split("\\."); int len = ver1.length > ver2.length ? ver1.length : ver2.length; for (int i = 0; i < len; i++) { String v1 = i < ver1.length ? ver1[i] : "0"; String v2 = i < ver2.length ? ver2[i] : "0"; int compare = strCmp(v1, v2); if (compare != 0) return compare; } return 0; } public int strCmp(String s1, String s2) { int len = s1.length() > s2.length() ? s1.length() : s2.length(); for (int i = 0; i < len; i++) { char v1 = i + s1.length() < len ? '0' : s1.charAt(i - len + s1.length()); char v2 = i + s2.length() < len ? '0' : s2.charAt(i - len + s2.length()); if (v1 > v2) return 1; if (v1 < v2) return -1; } return 0; }
http://www.geeksforgeeks.org/compare-two-version-numbers/
If we have more than two version then below versionCompare method can be used as cmp method of sort method, which will sort all versions according to specified comparison.

int versionCompare(string v1, string v2)

{

    //  vnum stores each numeric part of version

    int vnum1 = 0, vnum2 = 0;

    //  loop untill both string are processed

    for (int i=0,j=0; (i<v1.length() || j<v2.length()); )

{

        //  storing numeric part of version 1 in vnum1

        while (i < v1.length() && v1[i] != '.')

{

            vnum1 = vnum1 * 10 + (v1[i] - '0');

            i++;

}

        //  storing numeric part of version 2 in vnum2

        while (j < v2.length() && v2[j] != '.')

{

            vnum2 = vnum2 * 10 + (v2[j] - '0');

            j++;

}

        if (vnum1 > vnum2)

            return 1;

        if (vnum2 > vnum1)

            return -1;

        //  if equal, reset variables and go for next numeric

        // part

        vnum1 = vnum2 = 0;

        i++;

        j++;

}

    return 0;

}

Read full article from [leetcode] Compare Version Numbers - 追梦船的专栏 - 博客频道 - CSDN.NET

LeetCode 165 - Compare Version Numbers

Labels

Popular Posts