前言

哈喽大家好，我是雨墨，小老弟又来了，这是小老弟的第二篇博客，记录小老弟我刷字符串类型的leetcode 题目的笔记。每日更新3道，直至完成目标~
话不多说，咱们开始正题~~
目标已完成，本专题停止更新?

leetcode 344 反转字符串（开胃菜）

题目链接

传送门：https://leetcode-cn.com/problems/reverse-string/

我的题解

题目描述

编写一个函数，将字符串反转过来，要求必须原地修改字符串。

样例

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

算法

（双指针）$O(n)$

算法描述：使用两个指针，一个往后走，一个往前走，交换两个指针所指的元素，直到两个指针相遇，整个字符串就反转过来了。

class Solution {
public:
    void reverseString(vector<char>& s) {
        int len = s.size();

        for (int head = 0, tail = len - 1; head < tail; ++head, --tail) 
            swap(s[head], s[tail]);
    }
};

leetcode 541 反转字符串Ⅱ（换一个玩法）

题目链接

传送门：https://leetcode-cn.com/problems/reverse-string-ii/

我的题解

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

样例

输入：s = "abcdefg", k = 2
输出："bacdfeg"

算法

（模拟）$O(n)$

题目要求要在每2k个字符中选择前k个字符反转，那每次i += 2 * k就可以了，再多考虑数组长度满不满足大于 k 的情况就可以了。

class Solution {
public:
    string reverseStr(string s, int k) {
        int len = s.size();

        for (int i = 0; i < len; i += 2 * k) {
            int l = i, r = min(l + k, len);
            reverse(s.begin() + l, s.begin() + r);
        }

        return s;
    }
};

剑指offer 05 替换空格

题目链接

传送门：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/submissions/

我的题解

题目描述

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

样例

输入：s = "We are happy."
输出："We%20are%20happy."

算法1

（复制+替换）$O(n)$

将原字符串的内容拷贝到新的字符串内，如果遇到 ‘ ’， 就向新的字符串中添加%20。但是这种空间复杂度也是$O(n)$。

class Solution {
public:
    string replaceSpace(string s) {
        int len = s.size();
        string str;

        for (int i = 0; i < len; ++i) {
            if (s[i] != ' ')
                str += s[i];
            else str += "%20";
        }

        return str;
    }
};

算法2

（双指针）$O(n)$

先计算将空格替换之后新的字符串会变成多大的长度，然后对原字符串resize这个新的长度，一个指针i从原数组的尾部向头走，一个指针j从新的字符串尾部向头走，如果没有遇到空格，则直接s[j--] = s[i]，否则将空格转换成%20。这样空间复杂度为$O(1)$。

class Solution {   
public:
    string replaceSpace(string s) {
        int len = s.size(), new_len = 0;
        for (const auto& str : s) {
            if (str == ' ') new_len += 3;
            else new_len ++;
        }

        s.resize(new_len);

        for (int i = len - 1, j = new_len - 1; ~i; --i) {
            if (s[i] != ' ') s[j--] = s[i];
            else {
                s[j--] = '0';
                s[j--] = '2';
                s[j--] = '%';
            }
        }

        return s;
    }
};

leetcode 151 翻转字符串里的单词（好题，字符串重点题）

题目链接

传送门：https://leetcode-cn.com/problems/reverse-words-in-a-string/

我的题解

题目描述

给定一个字符串，逐个反转所有单词。

说明：

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

样例

输入：s = "  hello world  "
输出："world hello"

算法

（拆分问题）$O(n)$

这道题乍一看确实很难想，没办法一步到位，那就只好把这道题拆解逐个击破，这也是一种很重要的思想。

算法描述：

• 可以先将这个字符串全部反转
• 然后再逐个反转每个单题且保证每个单题之后以空格间隔，删去不必要的空格
• 更多实现细节见代码

class Solution {
public:
    string reverseWords(string s) {
        int len = s.size();
        reverse(s.begin(), s.end());    // 先将整个字符串翻转

        int beg_of_word = 0;    // 每个单词的开头
        for (int slowIndex = 0; slowIndex < len; ++slowIndex) {
            if (s[slowIndex] == ' ') continue;  // 找到第一个不是 ' ' 的字符
            int fastIndex = slowIndex, end_of_word = beg_of_word;
            // 寻找每一个完整的单词并用其覆盖原字符串 
            while (s[fastIndex] != ' ' && fastIndex < len) s[end_of_word++] = s[fastIndex++];
            // 翻转每个单词
            reverse(s.begin() + beg_of_word, s.begin() + end_of_word);
            s[end_of_word++] = ' '; // 在每个单词末尾添加 ' '
            beg_of_word = end_of_word, slowIndex = fastIndex;   // 更新
        }
        // 只要出现一个单词，那在其末尾一定会添加一个 ' '
        if (beg_of_word) --beg_of_word; 
        // 将末尾多余的 ' ' 删去
        s.erase(s.begin() + beg_of_word, s.end());

        return s;
    }
};

剑指offer 58 左旋转字符串

题目链接

传送门：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

我的题解

题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

样例

输入: s = "abcdefg", k = 2
输出: "cdefgab"

算法

（思维题）$O(n)$

这道题我是把难度调大了的，也就是在$O(1)$的空间复杂度下使得字符串左旋转。遇到问题一步不能到位，那就把它拆解，先reverse整个字符串一遍，将后 n 个字符串reverse一遍，再将前面的字符串reverse一遍，即可得到答案。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.end());
        reverse(s.end() - n, s.end());
        reverse(s.begin(), s.begin() + s.size() - n);

        return s;
    }
};

leetcode 28 实现 strStr()

题目链接

传送门：https://leetcode-cn.com/problems/implement-strstr/

我的题解

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

样例

输入：haystack = "hello", needle = "ll"
输出：2

算法1

（暴力）$O(nm)$

暴力非常不可取，耗时非常高。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        if (haystack.empty()) return -1;

        int len1 = haystack.size(), len2 = needle.size();
        
        int k = 0;
        int i = 0;
        for (; i < len1; ++i) {
            if (haystack[i] != needle[k]) continue;
            int j = i;
            while (j < len1 && haystack[j] == needle[k]) ++j, ++k;
            if (k != len2) k = 0;
            else break;
        }

        if (k != len2) return -1;
        else return i;
    }
};

算法2

（KMP)$O(n)$

快多了，这才是字符串匹配的正确打开方式 —– KMP，如果这次没有学会，那么就一定没有学会。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;

        int len1 = haystack.size(), len2 = needle.size();
        haystack = ' ' + haystack, needle = ' ' + needle;
        // 初始化 next[1] = 0
        vector<int> next(len2 + 1);
        // 求 next 数组过程
        // j 表示前缀末尾，也表示前后缀最大相等长度，i 表示后缀末尾
        for (int i = 2, j = 0; i <= len2; ++i) {    
            // 前后缀不相同
            while (j && needle[i] != needle[j + 1]) j = next[j];
            // 前后缀相同
            if (needle[i] == needle[j + 1]) ++j;
            next[i] = j;
        }

        // 匹配过程
        for (int i = 1, j = 0; i <= len1; ++i) {
            while (j && haystack[i] != needle[j + 1]) j = next[j];
            if (haystack[i] == needle[j + 1]) ++j;
            if (j == len2) return i - len2;
        }

        return -1;
    }
};

leetcode 459 重复的子字符串

题目链接

传送门：https://leetcode-cn.com/problems/repeated-substring-pattern/

我的题解

题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

样例

输入: "abab"
输出: True

算法

这道题应该被设置为 hard ，因为它本身是非常麻烦的，推导真的很麻烦，但是如果知道以下两个 KMP 的性质，就变得 easy 了。

• n - next[n] 是字符串的最小周期
• 如果周期可以整除 n ，那么最小周期的长度一定是其他所有周期的约数

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.size();
        s = ' ' + s;

        vector<int> next(len + 1);

        for (int i = 2, j = 0; i <= len; ++i) {
            while (j && s[i] != s[j + 1]) j = next[j];
            if (s[i] == s[j + 1]) ++j;
            next[i] = j;
        }

        int t = len - next[len];
        return t < len && len % t == 0;
    }
};

leetcode 13 罗马数字转整数

题目链接

传送门：https://leetcode-cn.com/problems/roman-to-integer/

我的题解

题目描述

已知罗马数字包含如下七种字符，每一个字符对应的数值为

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

通常情况下，罗马数字小的数在大的数字的右边，但也有特例：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

样例

输入: "III"
输出: 3

输入: "IV"
输出: 4

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3

算法

（模拟）$O(n)$

根据题意然后再模拟一遍，得到这样的结论：如果前一个数大于后一个数，那么结果就加上这个数，如果小于后一个数，那么结果就减去这个数。

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> hash;
        hash['I'] = 1, 
        hash['V'] = 5, 
        hash['X'] = 10, 
        hash['L'] = 50,
        hash['C'] = 100, 
        hash['D'] = 500,
        hash['M'] = 1000;

        int res = 0, len = s.size();
        for (int i = 0; i < len; ++i) {
            if (i + 1 < len && hash[s[i]] < hash[s[i + 1]])
                res -= hash[s[i]];
            else
                res += hash[s[i]];
        }

        return res;
    }
};

leetcode 67 二进制求和

题目链接

传送门：https://leetcode-cn.com/problems/add-binary/

我的题解

题目描述

给定两个二进制数，算出他俩之和。

样例

输入: a = "11", b = "1"
输出: "100"

算法

（高精度加法）$O(n)$

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        string res;
        int lenA = a.size(), lenB = b.size();
        for (int i = 0, t = 0; i < lenA || i < lenB || t; ++i) {
            if (i < lenA) t += a[i] - '0';
            if (i < lenB) t += b[i] - '0';
            res += to_string(t % 2);
            t /= 2;
        }

        reverse(res.begin(), res.end());
        
        return res;
    }
};

leetcode 434 字符串中的单词数

题目链接

传送门：https://leetcode-cn.com/problems/number-of-segments-in-a-string/

我的题解

题目描述

统计字符串中的单词个数。

样例

输入: "Hello, my name is John"
输出: 5

算法1

（双指针）$O(n)$

遇到单词遍历一遍，然后给结果加上1.

class Solution {
public:
    int countSegments(string s) {
        int len = s.size();
        int res = 0;

        for (int i = 0; i < len; ++i) {
            if (s[i] == ' ') continue;
            int j = i + 1;
            while (j < len && s[j] != ' ') ++j;
            ++res;
            i = j - 1;
        }

        return res;
    }
};

算法2

（规律）$O(n)$

这个办法很巧妙，它的意思是如果碰上空格，且它的前面的那个数不是空格，那么就是一个单词，因此需要在原字符串末尾加上一个空格。

class Solution {
public:
    int countSegments(string s) {
        int ans = 0;
        s += ' ';
        int len = s.size();

        for (int i = 1; i <= len; ++i) {
            if (s[i] == ' ' && s[i - 1] != ' ') 
                ++ans;
        }

        return ans;
    }
};

leetcode 819 最常见的单词

题目链接

传送门：https://leetcode-cn.com/problems/most-common-word/

我的题解

题目描述

给定一个段落以及一个被 ban 的单词列表，要求返回本段落中出现次数最多的单词，段落中有大写单词，答案必须是小写字母，被 ban 的单词不得出现在答案中。

样例

输入: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"

算法

（哈希表）$O(n)$

题目一看就是使用哈希表做，本题的难点我认为是如何将每个单词存入哈希表中（见代码），因为 paragraph 是一个字符串，这里使用了 isalpha()函数，判断当前的 char 是不是字母，由于题目要求返回小写字母，故还需要使用 tolower()函数。

class Solution {
public:
    string mostCommonWord(string paragraph, vector<string>& banned) {
        unordered_set<string> ban(banned.begin(), banned.end());
        unordered_map<string, int> cnt;
        string word;	// 单词

        for (auto str : paragraph) {
            str = tolower(str);
            if (isalpha(str)) word += str;
            else {
                if (!word.empty()) {
                    if (!ban.count(word)) ++cnt[word];
                    word.clear();	// 清空单词
                }
            }
        }
        if (!word.empty() && !ban.count(word)) ++cnt[word];

        string ans;
        // 遍历哈希表，寻找出现次数最多的单词
        for (auto& [str, nu] : cnt) {
            if (cnt[ans] < nu) 
                ans = str;
        }

        return ans;
    }
};

leetcode 859 亲密字符串

题目链接

传送门：https://leetcode-cn.com/problems/buddy-strings/

我的题解

给定两个小写字母构成的字符串A和B，如果通过交换A的两个字母就能与B相同，则return true，否则return false。

样例

输入： A = "ab", B = "ba"
输出： true

输入： A = "ab", B = "ab"
输出： false

输入： A = "aa", B = "aa"
输出： true

算法

（模拟）$O(n)$

需要考虑两种情况：

• 如果 A == B，就像样例中的第二、三个例子，如果A交换的两个字母相同，那么就为true，否则为false，那如何判断A交换的两个字母相同呢，可以用哈希表记录，如果A中有两个字母相同，那么就一定交换之后还相同。
• 如果 A != B，就像样例中的第一个例子，可以这样来判断，A与B不同的字母分别记为A[first]，B[first],第二个不相同的记为A[second]，以及B[second]，如果 A[first] == B[second] && A[second] == B[first] && A 和 B 就只有这两个不相同的字母，则return true，否则return false。记录first以及second可以使用 vector存储。

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s.size() != goal.size()) return false;
        int len = s.size();
        
        if (s == goal) {
            unordered_map<char, int> cnt;
            for (const auto& c : s) {
                if (++cnt[c] == 2) return true;
            }
            return false; 
        }

        vector<int> pos;
        for (int i = 0; i < len; ++i) 
            if (s[i] != goal[i]) 
                pos.push_back(i);
        
        if (pos.size() != 2) return false;
        int first = pos[0], second = pos[1];
        if (s[first] == goal[second] && s[second] == goal[first]) return true;
        return false;
    }
};

leetcode 686 重复叠加字符串匹配 （好题）

题目链接

传送门：https://leetcode-cn.com/problems/repeated-string-match/

我的题解

题目描述

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

**注意：**字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

样例

输入：a = "abcd", b = "cdabcdab"
输出：3

算法

（KMP）$O(n)$

算法描述：首先得让字符串a叠加之后的长度大于等于b，但这还不够，原因是，不知道b是从叠加之后的字符串的哪一个起点开始匹配，所以还得在末尾多加一段a。然后就是用KMP判断b能否能与a叠加之后的字符串匹配，如果匹配成功，由于题目要求的是返回叠加的次数，那必然是最后匹配的下标和a.size()相除，向上取整，向上取整的方法 CSAPP 上有讲述。

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        string s;
        while (s.size() < b.size()) s += a;
        s += a;
        int n = s.size(), m = b.size();
        s = ' ' + s, b = ' ' + b;
        
        vector<int> next(n + 1);
        for (int i = 2, j = 0; i <= m; ++i) {
            while (j && b[i] != b[j + 1]) j = next[j];
            if (b[i] == b[j + 1]) ++j;
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= n; ++i) {
            while (j && s[i] != b[j + 1]) j = next[j];
            if (s[i] == b[j + 1]) ++j;
            if (j == m) return (i + a.size() - 1) / a.size();
        }

        return -1;
    }
};

leetcode 680 验证回文字符串Ⅱ （重点在于思路）

题目链接

传送门：https://leetcode-cn.com/problems/valid-palindrome-ii/

我的题解

题目描述

给定一个非空字符串 s ，最多删除一个字符，判断是否能成为回文字符串。

样例

输入: s = "abca"
输出: true

算法

（贪心）$O(n)$

回文字符串就是从头读和从尾读都是一样的字符串，肯定想到的是使用双指针i和j来读（即两个指针所指字符相等，那么都往中间移一位），如果最终两个指针相遇，说明是回文串。题目的意思是问如果不相等，那删除一个可不可以变成回文串，那么就可以右移i，判断剩余段是否能构成回文串，或是左移j，判断剩余串能否构成回文串。因此，问题也就等价于能够在原串中找到这样的字串。

class Solution {
public:
    bool check(string& s, int beg, int end) {
        while (beg < end) {
            if (s[beg] != s[end]) return false;
            ++beg, --end;
        }

        return true;
    }

    bool validPalindrome(string s) {
        int len = s.size();
        
        for (int beg = 0, end = len - 1; beg < end; ++beg, --end) {
            if (s[beg] != s[end]) {
                if (check(s, beg + 1, end) || check(s, beg, end - 1)) return true;
                return false;
            }
        }
        return true;
    }
};

leetcode 6 Z字形变换 （规律题）

题目链接

传送门：https://leetcode-cn.com/problems/zigzag-conversion/

我的题解

题目描述

给定一个字符串s以及行号numRows，从上往下呈 Z 字形排列，逐行输出字符串。

样例

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

算法

（模拟）$O(n)$

这题是道找规律的题，具体见图：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string ans;
        int len = s.size();

        for (int row = 0; row < numRows; ++row) {
            if (row == 0 || row == numRows - 1) {	// 图中第一种情况
                for (int i = row; i < len; i += 2 * numRows - 2) 
                    ans += s[i];
            } else {	// 图中第二种情况
                for (int i = row, j = 2 * numRows - 2 - i; i < len || j < len;
                    i += 2 * numRows - 2, j += 2 * numRows - 2) {
                    if (i < len) ans += s[i];
                    if (j < len) ans += s[j];
                }
            }
        }

        return ans;
    }
};

leetcode 8 字符串转整数 （主要是看整数溢出）

题目链接

传送门：https://leetcode-cn.com/problems/string-to-integer-atoi/

我的题解

题目描述

自己实现一个字符串转整数的函数，要求：

• 去除前导空格
• 去除前导 0
• 如果第一个非空格字符不是数字，return 0
• 注意 + 和 - 号
• 如果正溢出，返回 $2^{31}-1$，如果是负溢出，返回 $-2^{31}$

样例

输入：s = "   -42"
输出：-42

输入：s = "4193 with words"
输出：4193

输入：s = "words and 987"
输出：0

算法

（模拟）$O(n)$

题目最主要的是讨论溢出的情况，其余的就是把满足题意的条件考虑完，其余的不满足的就不需要考虑了，如果返回结果是long long的话，就不用考虑溢出的情况，但是如果返回结果是int类型的话，就必须要考虑清楚溢出的情况了。详见代码：

class Solution {
public:
    int myAtoi(string s) {
        // 去除前导空格
        int k = 0, len = s.size();
        while (k < len && s[k] == ' ') ++k;
        if (k == len) return 0;

        int flag = 1;
        if (s[k] == '-') flag = -1, ++k;
        else if (s[k] == '+') ++k;

        // long long ans = 0;
        int ans = 0;
        while (k < len && s[k] >= '0' && s[k] <= '9') {
            int tmp = s[k] - '0';
            if (flag == 1 && ans > (INT_MAX - tmp) / 10) return INT_MAX;
            if (flag == -1 && -ans < (INT_MIN + tmp) / 10) return INT_MIN;
            if (flag == -1 && -ans * 10 - tmp == INT_MIN) return INT_MIN;	// 如果缺少这一行，那么下一行就会溢出
            ans = ans * 10 + tmp;
            ++k;
            if (ans > INT_MAX) break;
        }

        ans *= flag; 
        if (ans > INT_MAX) ans = INT_MAX;
        if (ans < INT_MIN) ans = INT_MIN;

        return ans;
    }
};

leetcode 17 电话号码的字母组合

题目链接

传送门：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

我的题解

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

样例

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

算法

**（dfs）**最坏的情况下：$O(n{4}^n)$

这道题，属于排列组合的问题，特别适合 dfs 来做。因为 dfs 可以把所有可能的结果都给你走个遍！

时间复杂度：最坏的情况下，也就是含 9 ，有四种选择，因此是 $4^n$ 次，然后还有一次 push_back 操作，所以最坏的时间复杂度是 $O(n{4}^n)$。

class Solution {
public:
    // 存取键位对应的值
    unordered_map<int, string> keyMap = {
        {1, ""},
        {2, "abc"},
        {3, "def"},
        {4, "ghi"},
        {5, "jkl"},
        {6, "mno"},
        {7, "pqrs"},
        {8, "tuv"},
        {9, "wxyz"}
    };
    vector<string> combination; // 结果

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return combination;
        dfs(digits, 0, ""); 

        return combination;
    }
    
    void dfs(string& digits, int u, string path) {
        if (u == digits.size()) combination.push_back(path);
        else {
            for (const auto& c : keyMap[digits[u] - '0']) {
                dfs(digits, u + 1, path + c);
            }
        }
    }
};

leetcode 165 比较版本号

题目链接

传送门：https://leetcode-cn.com/problems/compare-version-numbers/submissions/

我的题解

题目描述

给定两个版本号 version1 和 version2 ，比较两个版本号谁大谁小。已知每个版本号由一个或多个修订号组成，每个修订号由 ‘.’ 连接，注意修订号可能有前导零。比较版本号时，按照从左到右的顺序比较它们的修订号，比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。

返回规则：

• 如果 version1 > version2 返回 1，
• 如果 version1 < version2 返回 -1，
• 除此之外返回 0。

样例

输入：version1 = "1.01", version2 = "1.001"
输出：0

算法

（双指针）$O(n)$

其实这道题思路很好想，寻找 ‘.’ ，比较其之前或之后的字符串组成的数字。
不知道大家有没有遇到我这种情况，遇到题有思路，但写不对…比如这道题我知道使用双指针，但是如何将字符串转换成数字我并不知道，还傻傻的去写一个函数实现这样的功能，还没能做对?，其实stoi函数就可以实现这样的功能，但是，在这之前，根本不知道可以用这个函数 + substr很轻松就解决这道题，所以还得多做题。

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int sz1 = version1.size(), sz2 = version2.size();
        for (int slowIndex1 = 0, slowIndex2 = 0; slowIndex1 < sz1 || slowIndex2 < sz2;) {
            int fastIndex1 = slowIndex1, fastIndex2 = slowIndex2;
            while (fastIndex1 < sz1 && version1[fastIndex1] != '.') ++fastIndex1;
            while (fastIndex2 < sz2 && version2[fastIndex2] != '.') ++fastIndex2;

            int tmp1 = (fastIndex1 == slowIndex1 ? 0 : stoi(version1.substr(slowIndex1, 
                        fastIndex1 - slowIndex1)));
            int tmp2 = (fastIndex2 == slowIndex2 ? 0 : stoi(version2.substr(slowIndex2, 
                        fastIndex2 - slowIndex2)));

            if (tmp1 < tmp2) return -1;
            else if (tmp1 > tmp2) return 1;

            slowIndex1 = fastIndex1 + 1, slowIndex2 = fastIndex2 + 1;
        }
            
        return 0;
    }
};