165. Compare Version Numbers

November 10, 2016

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.152.2,前者相对后者属于更新的版本,因为前者指第二阶段第十五个版本,而后者是第五个。

2.对于1.01,是同一个版本。

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

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

之所以要立刻进行比较,是因为,以13.28.3513.30.36做比较,当我们比较到中间的两位数字2830之后,实际上已经分出了新旧版本关系,完全不必去比较3536的关系。

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

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;
    }
};

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017