题目：
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
链接： http://leetcode.com/problems/compare-version-numbers/
题解：
比较版本大小。这道题目可以把输入两个string split一下，注意因为"."是特殊regex，所以要用"\\."。Split完毕以后比较array每个对应元素的大小就可以了。
Time Complexity - O(n)， Splace Complexity - O(n)。
public class Solution {
public int compareVersion(String version1, String version2) {
if(version1 == null || version2 == null)
return 0;
String[] version1Arr = version1.split("\\.");
String[] version2Arr = version2.split("\\.");
int i = 0, j = 0;
while(i < version1Arr.length || j < version2Arr.length) {
int ver1 = i < version1Arr.length ? Integer.parseInt(version1Arr[i]) : 0;
int ver2 = j < version2Arr.length ? Integer.parseInt(version2Arr[i]) : 0;
if(ver1 < ver2)
return -1;
else if(ver1 > ver2)
return 1;
i++;
j++;
}
return 0;
}
}
假如不想用split，那么可以节约space complexity。这里我们不用parseInt，要使用手动计算每个level version的数字，然后加以比较。
Time Complexity - O(n)， Space Complexity - O(1)
public class Solution {
public int compareVersion(String version1, String version2) {
if(version1 == null || version2 == null)
return 0;
int ver1 = 0, ver2 = 0, i = 0, j = 0;
while(i < version1.length() || j < version2.length()){
while(i < version1.length() && version1.charAt(i) != '.'){
ver1 = ver1 * 10 + version1.charAt(i) - '0';
i++;
}
while(j < version2.length() && version2.charAt(j) != '.' ){
ver2 = ver2 * 10 + version2.charAt(j) - '0';
j++;
}
if(ver1 < ver2)
return -1;
else if(ver1 > ver2)
return 1;
else{
ver1 = 0;
ver2 = 0;
i++;
j++;
}
}
return 0;
}
}
题外话: 双11特意Work from home在家抢宝贝，不过总觉得没啥可买的，浏览来浏览去，到最后也只花了600多块，买了几本书和一个行车记录仪...不够阔气啊，于是订了Jewel Bako明天去找找感觉。
二刷:
方法跟一刷一样
Java:
Time Complexity - O(n)， Splace Complexity - O(n)。
public class Solution {
public int compareVersion(String version1, String version2) {
if (version1 == null || version2 == null) {
return 0;
}
String[] ver1Arr = version1.split("\\.");
String[] ver2Arr = version2.split("\\.");
int len1 = ver1Arr.length, len2 = ver2Arr.length, lo1 = 0, lo2 = 0;
while (lo1 < len1 || lo2 < len2) {
int ver1 = lo1 < len1 ? Integer.parseInt(ver1Arr[lo1]) : 0;
int ver2 = lo2 < len2 ? Integer.parseInt(ver2Arr[lo2]) : 0;
if (ver1 < ver2) {
return -1;
} else if (ver1 > ver2) {
return 1;
} else {
lo1++;
lo2++;
}
}
return 0;
}
}
不用split
Time Complexity - O(n)， Space Complexity - O(1)
public class Solution {
public int compareVersion(String version1, String version2) {
if (version1 == null || version2 == null) {
return 0;
}
int len1 = version1.length(), len2 = version2.length(), lo1 = 0, lo2 = 0, ver1 = 0, ver2 = 0;
while (lo1 < len1 || lo2 < len2) {
while (lo1 < len1 && version1.charAt(lo1) != '.') {
ver1 = 10 * ver1 + version1.charAt(lo1) - '0';
lo1++;
}
while (lo2 < len2 && version2.charAt(lo2) != '.') {
ver2 = 10 * ver2 + version2.charAt(lo2) - '0';
lo2++;
}
if (ver1 < ver2) {
return -1;
} else if (ver1 > ver2) {
return 1;
} else {
lo1++;
lo2++;
ver1 = 0;
ver2 = 0;
}
}
return 0;
}
}
三刷:
Java:
public class Solution {
public int compareVersion(String version1, String version2) {
if (version1 == null || version2 == null) return 0;
String[] v1s = version1.split("\\.");
String[] v2s = version2.split("\\.");
int i = 0, j = 0, res = 0;
while (i < v1s.length || j < v2s.length) {
int ver1 = i < v1s.length ? Integer.valueOf(v1s[i++]) : 0;
int ver2 = j < v2s.length ? Integer.valueOf(v2s[j++]) : 0;
if (ver1 < ver2) return -1;
else if (ver1 > ver2) return 1;
}
return 0;
}
}
Reference：
http://www.fromdev.com/2009/10/playing-with-java-string-split-basics.html