Saturday, January 3, 2015

Compare Version Numbers

Q:
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


A:
思路就是一个个取出来比较。

public class Solution {
    public int compareVersion(String version1, String version2) {
        version1=version1.trim();
        version2 = version2.trim();
        if(version1.length()==0)
            return version2.length()==0?0:(isZero(version2)?0:-1);
        if(version2.length()==0)
            return version1.length()==0?0:(isZero(version1)?0:1);
        
        int i1 = version1.indexOf('.'), i2 = version2.indexOf('.');
        int n1,n2;
        
        if(i1 == -1){
            n1 = Integer.parseInt(version1);
            version1 = "";
        }else{
            n1 = Integer.parseInt(version1.substring(0,i1));
            version1 = version1.substring(i1+1);
        }
        
        if(i2 == -1){
            n2 = Integer.parseInt(version2);
            version2 = "";
        }else{
            n2 = Integer.parseInt(version2.substring(0,i2));
            version2 = version2.substring(i2+1);
        }
        return n1==n2?compareVersion(version1,version2):(n1>n2?1:-1);
    }
    public boolean isZero(String str){
        if(str.length()==0)
            return true;
            
        char ch = str.charAt(0);
        if(ch =='0' || ch=='.')
            return isZero(str.substring(1));
        else
            return false;
    }
}



Mistakes:
没考虑这种情况:
1:   1.0   和  1
2:   1.000.00 和 1

-----------第二遍-----犯了同样的错误-----------------

public class Solution {
    public int compareVersion(String version1, String version2) {
        List<Integer> l1 = new LinkedList<>(), l2 = new LinkedList<>();
        for(String ss: version1.split("\\.")) 
            l1.add(Integer.parseInt(ss));
        for(String ss : version2.split("\\."))
            l2.add(Integer.parseInt(ss));
        int m = l1.size(), n = l2.size();
        for(int i =0;i< Math.max(m,n);i++){
            int a =i>=m?0:l1.get(i), b = i>=n?0:l2.get(i);
            if(a>b)
                return 1;
            else if(a<b)
                return -1;
        }
        return 0;
    }
}



No comments:

Post a Comment