题目

题解

1. stringstream法

用stringstream和getline切割字符串，并挨个比较，本来想用getline的，但是这样while循环不好写，若写出或结构有短路操作，若getline()外面套个bool，while循环是可以写了，但是若两个字符串.的个数不一样又会有新的问题，因此还是乖乖用»

  • 时间复杂度$O(max{m,n})$
  • 空间复杂度$O(1)$
class Solution {
public:
    int compareVersion(string version1, string version2) {
        stringstream s1(version1+"."), s2(version2+".");//加个.使字符串更规范，用>>更方便
        char dot = '.';//用dot保存'.'，注意用char
        int val1, val2;
        while(s1.good() || s2.good()){
            s1>>val1>>dot;
            s2>>val2>>dot;
            if(val1 < val2) return -1;
            else if(val1 > val2) return 1;//进行比较
            val1 = val2 =0;
        }
        return 0;
    }
};

2. 双指针法

两个指针挨个后移，取数比较，注意while循环个终止条件和里面两个while地循环终止条件

  • 时间复杂度$O(N)$
  • 空间复杂度$O(1)$
class Solution {
public:
    int compareVersion(string version1, string version2) {
        int p1 = 0, p2 = 0;//双指针
        int n = max(version1.size(), version2.size());//取两个里面长的作为总遍历长度
        while(p1<n || p2<n){//有一个没超过end就继续遍历
            int val1 = 0, val2 = 0;//暂存当前值
            while(p1<version1.size() && version1[p1]!='.'){
                val1 = val1*10 + version1[p1++]-'0';
            }//取当前值，到'.'停，挨个取数并×10再加在一起
            while(p2<version2.size() && version2[p2]!='.'){
                val2 = val2*10 + version2[p2++]-'0';
            }//同上
            if(val1 > val2) return 1;
            else if(val1 < val2) return -1;//进行比较
            p1++;
            p2++;//两个指针后移，此时两个可能在末尾或者在'.'处
        }
        return 0;
    }
};