LeetCode: 165. 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.

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

解题思路

模拟，依次比较每个版本号。

AC 代码

class Solution {
    vector<int> splitVersion(string version)
    {
        vector<int> verNums;

        int beg = 0, end = 0;
        while((end = version.find_first_of('.', beg)) != version.npos || beg < version.size())
        {
            if(end == version.npos) end = version.size();
            string subVersion = version.substr(beg, end-beg);
            verNums.push_back(stoi(subVersion));

            beg = end+1;
        }

        return verNums;
    }
    int compareVersion(const vector<int>& ver1, const vector<int>& ver2, int idx)
    {
        if(idx >= ver1.size() && idx >= ver2.size()) return 0;
        else if(idx >= ver1.size() && ver2[idx] != 0) return -1;
        else if(idx >= ver1.size() && ver2[idx] == 0) return compareVersion(ver1, ver2, idx+1);
        else if(idx >= ver2.size() && ver1[idx] != 0) return 1;
        else if(idx >= ver2.size() && ver1[idx] == 0) return compareVersion(ver1, ver2, idx+1);
        else if(ver1[idx] == ver2[idx])  return compareVersion(ver1, ver2, idx+1);
        else if(ver1[idx] > ver2[idx]) return 1;
        else return -1;
    }
public:
    int compareVersion(string version1, string version2) {

        return compareVersion(splitVersion(version1), splitVersion(version2), 0);
    }
};