2015年10月24日星期六

Leetcode 165 Compare Version Numbers

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.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
Solution 1: Two pointers for s and t. compare the numbers before it reach '.' or end of string. If one pointer go beyond the end of string, use default value of 0.
 public class Solution {  
   public int compareVersion(String version1, String version2) {  
     int i=0, j=0;  
     int m=version1.length(), n=version2.length();  
     while (i<m || j<n) {  
       int p1=i;  
       while (p1<m && version1.charAt(p1)!='.') p1++;  
       int num1=(p1>i)?Integer.valueOf(version1.substring(i,p1)):0;  
       int p2=j;  
       while (p2<n && version2.charAt(p2)!='.') p2++;  
       int num2=(p2>j)?Integer.valueOf(version2.substring(j,p2)):0;  
       if (num1>num2) return 1;  
       if (num1<num2) return -1;  
       i=++p1;  
       j=++p2;  
     }  
     return 0;  
   }  
 }  
Solution 2: Similar
 public class Solution {  
   public int compareVersion(String version1, String version2) {  
     String[] v1=version1.split("\\.");  
     String[] v2=version2.split("\\.");  
     for (int i=0; i<v1.length || i<v2.length; i++) {  
       int num1=i<v1.length?Integer.valueOf(v1[i]):0;  
       int num2=i<v2.length?Integer.valueOf(v2[i]):0;  
       if (num1>num2) return 1;  
       else if (num1<num2) return -1;  
     }  
     return 0;  
   }  
 }  

没有评论:

发表评论