[LeetCode]165.Compare Version Numbers

【题目】

Compare two version numbers version1 and version1.
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

【分析】

类似于split的方法把字符串解析, 然后再比较。

（1）将两个字符串version1和version2进行分割，因为可能会出现这样的测试用例"1.0.1"，有多个点。

（2）容器vector存储按照"."分割之后的数字。

（3）然后依次进行比较。

【代码】

    /**------------------------------------
    *   日期：2015-02-02
    *   作者：SJF0115
    *   题目: 165.Compare Version Numbers
    *   网址：https://oj.leetcode.com/problems/compare-version-numbers/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        int compareVersion(string version1, string version2) {
            int size1 = version1.size();
            int size2 = version2.size();
            vector<int> v1;
            vector<int> v2;
            // 解析version1
            int sum = 0;
            for(int i = 0;i < size1;++i){
                if(version1[i] == '.'){
                    v1.push_back(sum);
                    sum = 0;
                }//if
                else{
                    sum = sum * 10 + version1[i] - '0';
                }//else
            }//for
            v1.push_back(sum);
            // 解析version2
            sum = 0;
            for(int i = 0;i < size2;++i){
                if(version2[i] == '.'){
                    v2.push_back(sum);
                    sum = 0;
                }//if
                else{
                    sum = sum * 10 + version2[i] - '0';
                }//else
            }//for
            v2.push_back(sum);
            // 比较
            int count1 = v1.size();
            int count2 = v2.size();
            int num1,num2;
            for(int i = 0,j = 0;i < count1 || j < count2;++i,++j){
                num1 = i < count1 ? v1[i] : 0;
                num2 = j < count2 ? v2[j] : 0;
                if(num1 > num2){
                    return 1;
                }//if
                else if(num1 < num2){
                    return -1;
                }//else
            }//for
            return 0;
        }
    };

    int main(){
        Solution s;
        string str1("1.1");
        //string str1("13.27.24");
        string str2("1.1");
        int result = s.compareVersion(str1,str2);
        // 输出
        cout<<result<<endl;
        return 0;
    }

【思路二】

思路二是对思路一的优化，思路一中，必须把version1,version2都解析完全才能比较。

例如：version1 = "13.27.23"  version2 = "13.28.25"

思路一中23和25都会遍历到，这其实对结果没有什么影响了，因为前面的27和28已经决定了哪个版本的大小了，因此我们可以不必要解析后面的字符串。

基于这样的思路我们边解析边比较，一旦有结果便停止解析。

【代码二】

    /**------------------------------------
    *   日期：2015-02-02
    *   作者：SJF0115
    *   题目: 165.Compare Version Numbers
    *   网址：https://oj.leetcode.com/problems/compare-version-numbers/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/

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