165. Compare Version Numbers.md

165. Compare Version Numbers

Questions:

Compare two version numbers version1 and version2. 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.

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Thinking:

• Method 1:
  • 要注意在使用split的时候"."需要使用转义字符"\."

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

二刷

1. 还是要注意使用转义字符，因为.在正则中是单字符匹配。
2. 从字符串转成整形有两种方法，一种是Integer.valueOf()，第二种是Integer.parseInt(),似乎valueOf方法更快一些。

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] arr1 = version1.split("\\.");        
        String[] arr2 = version2.split("\\.");
        int len1 = arr1.length, len2 = arr2.length;
        int index1 = 0, index2 = 0;
        while(index1 < len1 && index2 < len2){
            Integer token1 = Integer.valueOf(arr1[index1++]);
            Integer token2 = Integer.valueOf(arr2[index2++]);
            if(token1 < token2) return -1;
            else if(token1 > token2) return 1;
        }
        if(index1 == len1){
            while(index2 < len2){
                if(Integer.valueOf(arr2[index2++]) != 0)
                    return -1;
            }
        }else{
            while(index1 < len1){
                if(Integer.valueOf(arr1[index1++]) != 0)
                    return 1;
            }
        }
        return 0;
    }
}

Third Time

• Method 1: String

   class Solution {
   	public int compareVersion(String version1, String version2) {
   		String[] v1 = version1.split("\\.");
   		String[] v2 = version2.split("\\.");
   		int count1 = 0, count2 = 0;
   		while(count1 < v1.length || count2 < v2.length){
   			if(count1 < v1.length && count2 < v2.length){
   				int v1Num = Integer.parseInt(v1[count1++]);
   				int v2Num = Integer.parseInt(v2[count2++]);
   				if(v1Num < v2Num) return -1;
   				else if(v1Num > v2Num) return 1;
   			}else if(count1 < v1.length){
   				int v1Num = Integer.parseInt(v1[count1++]);
   				if(v1Num > 0) return 1;
   			}else{
   				int v2Num = Integer.parseInt(v2[count2++]);
   				if(v2Num > 0) return -1;
   			}
   		}
   		return 0;
   	}
   }

Amazon Session

• Method 1: String

   class Solution {
   	public int compareVersion(String version1, String version2) {
   		String[] tokens1 = version1.split("\\.");
   		String[] tokens2 = version2.split("\\.");
   		int index = 0;
   		while(index < tokens1.length || index < tokens2.length){
   			if(index < tokens1.length && index < tokens2.length){
   				int first = Integer.parseInt(tokens1[index]);
   				int second = Integer.parseInt(tokens2[index]);
   				if(first < second) return -1;
   				else if(first > second) return 1;
   			}else if(index < tokens1.length){
   				int first = Integer.parseInt(tokens1[index]);
   				if(first != 0) return 1;
   			}else if(index < tokens2.length){
   				int second = Integer.parseInt(tokens2[index]);
   				if(second != 0) return -1;
   			}
   			index++;
   		}
   		return 0;
   	}
   }