165. Compare Version Numbers

Description

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

Analysis

这道题要求对两个字符串组成的版本号进行比较，以确定哪一个版本较新，对于版本号，我们不能够将其简单的看作浮点数进行比较，下面给出几个例子以便对版本号的比较有一个初步的认识.

1.对于2.15和2.2，前者相对后者属于更新的版本，因为前者指第二阶段第十五个版本，而后者是第五个。

2.对于1.0和1，是同一个版本。

所以，如果我们想当然地认为浮点数2.2大于2.15，所以在版本号系统中亦如此，那就大错特错了。

所以要对版本号进行比较的话，我们需要对两个字符串进行遍历，之后以’.’为界限，计算两个’.’之间的数值，每分割出一个这样的子串并计算出其整型值之后，可以立刻进行比较。

之所以要立刻进行比较，是因为，以13.28.35和13.30.36做比较，当我们比较到中间的两位数字28和30之后，实际上已经分出了新旧版本关系，完全不必去比较35和36的关系。

给出如下代码，看完代码思路应该会很清楚。

Code

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int v1_size=version1.size();
        int v2_size=version2.size();
        int sum1=0,sum2=0;
        int i=0,j=0;
        for(i=0,j=0;i<v1_size||j<v2_size;++i,++j){
            sum1=0;
            while(i<v1_size&&version1[i]!='.'){
                sum1=sum1*10+version1[i]-'0';
                ++i;
            }
            sum2=0;
            while(j<v2_size&&version2[j]!='.'){
                sum2=sum2*10+version2[j]-'0';
                ++j;
            }
            if(sum1>sum2)
                return 1;
            else if(sum1<sum2)
                return -1;
        }
        return 0;
    }
};