問(wèn)題

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.

例子

0.1 < 1.1 < 1.2 < 13.37

分析

題目沒(méi)有說(shuō)明.出現(xiàn)的次數(shù)，實(shí)際上10.7.3.0.1這種版本號(hào)也是合法的垮耳。3.0.0這種以0為結(jié)尾的版本號(hào)同樣是合法的终佛。

自己實(shí)現(xiàn)一個(gè)split方法铃彰，將版本號(hào)根據(jù).號(hào)切割成若干版本數(shù)字牙捉，然后從左到右依次比較大小唬党。要注意3.0和3.0.0這種情況驶拱，兩者是相等的版本號(hào)。

要點(diǎn)

• 切割字符串
• 比較大幸趺稀（類比sort算法的comparator函數(shù)）

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

O(n)

代碼

class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> versions1, versions2;
        split(version1, ".", versions1);
        split(version2, ".", versions2);
        int i = 0;
        for (; i < versions1.size() && i < versions2.size(); i++) {
            if (versions1[i] > versions2[i]) return 1;
            if (versions1[i] < versions2[i]) return -1;
        }
        for (; i < versions1.size(); i++)
            if (versions1[i] != 0) return 1;
        for (; i < versions2.size(); i++)
            if (versions2[i] != 0) return -1;
            
        return 0;
    }
    
private:
    void split(const std::string &s, std::string delim, std::vector<int> &res) {
        size_t last = 0;
        size_t index = s.find_first_of(delim, last);
        while (index != std::string::npos) {
            if (index > last) res.push_back(stoi(s.substr(last, index - last)));
            last = index + 1;
            index = s.find_first_of(delim, last);
        }
        if (index > last)
            res.push_back(stoi(s.substr(last, index - last)));
    }
};

直接遍歷字符

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