[LeetCode]165.Compare Version Numbers

[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 
    #include 
    #include 
    using namespace std;

    class Solution {
    public:
        int compareVersion(string version1, string version2) {
            int size1 = version1.size();
            int size2 = version2.size();
            vector v1;
            vector 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<




【思路二】
思路二是對思路一的優化，思路一中，必須把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;
        }
    };