[leetcode] Compare Version Numbers


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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

tags: string

一开始看到这题时,其实我是,是拒绝的。因为觉得只要一个stof函数,把字符串转换成浮点数就可以。

但是我错了。

第一,可能有多个小数点;

第二,1.1 版本和1.10版本不同,后者更大。

所以我们以小数点为分隔符,每次比较两个小数点之间的数字。当遇到版本号小数点的个数不同时,如果剩余的那个版本号的剩余字段不都为0,则字段多的那个版本号更大。

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int i = 0; 
        int j = 0;
        while(true){
            if(i == version1.size() && j == version2.size()){
                return 0;
            }
            int start1 = version1[i] == '.'? ++i: i;
            int start2 = version2[j] == '.'? ++j: j;
            while(version1[i] != '.' && i < version1.size()){
                i++;
            }
            while(version2[j] != '.' && j < version2.size()){
                j++;
            }
            int a = stoi(version1.substr(start1, i - start1));
            int b = stoi(version2.substr(start2, j - start2));
            if(a > b){
                return 1;
            }
            else if(a < b){
                return -1;
            }
            else{
                continue;
            }
        }
    }
    int stoi(string s){
        int sum = 0;
        for(int i = 0; i < s.size(); i++){
            sum = sum * 10 + s[i] - '0';
        }
        return sum;
    }
};

Untitled

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.