Leetcode 165 - Compare Version Numbers

題目

Problem#

題目給你兩個版本號，要你比較大小

想法#

照做即可

• 時間複雜度: $\mathcal{O}(N)$
• 空間複雜度: $\mathcal{O}(N)$

AC Code#

Copy

class Solution
{
public:
    void split(string &s, vector<int> &n)
    {
        int cur = 0;
        for(char c : s)
        {
            if(c == '.')
            {
                n.push_back(cur);
                cur = 0;
                continue;
            }
            cur *= 10;
            cur += c - '0';
        }
 
        n.push_back(cur);
    }
    
    // >
    int compareVersion(string a, string b)
    {
        vector<int> A, B;
        
        split(a, A);
        split(b, B);
 
        vector<int> *p = nullptr;
        int siz = max(A.size(), B.size());
        if(A.size() != siz)
            p = &A;
        else if(B.size() != siz)
            p = &B;
        if(p)
        {
            vector<int> &v = *p;
 
            for(int i = v.size(); i < siz; i++)
                v.push_back(0);
        }
 
        DBG(A);
        DBG(B);
 
        int i;
        for(i = 0; i < siz; i++)
        {
            if(A[i] != B[i])
                break;
        }
 
        return i == siz ? 0 : (A[i]>B[i] ? 1 : -1);
    }
};

view raw leetcode/165.cpp delivered with ❤ by emgithub

賞析#

None