6.数字与字符串之间转换

299:使用额外两个数组记录Bulls,cows

6-1.相对名次：506

make_pair(a,b):形成诸如pair<int,int>的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        vector<pair<int, int>> arr;
        int n = score.size();
        string rankTop[3] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        for (int i = 0; i < n; i++) {
            arr.emplace_back(
                make_pair(-score[i], i)); //-score[i]以保证sort排序时由大到小
        }
        sort(arr.begin(), arr.end());//根据arr[index].first的大小排序
        vector<string> res(n);
        for (int i = 0; i < n; i++) {
            if (i < 3) {
                res[arr[i].second] = rankTop[i];//arr[i].second记录原下标
            } else {
                res[arr[i].second] = to_string(i + 1);
            }
        }
        return res;
    }
};

在C++中，arr可以是任何支持随机访问迭代器的容器类型，例如：

  • std::vector
  • std::array
  • std::deque
  • std::string
  • 内置数组（例如int arr[5]）

这些类型都支持begin()和end()成员函数，因此可以作为sort函数的参数。

vector中每个元素都是pair类型时，也可以使用sort函数。因为vector<pair<T1, T2>>支持随机访问迭代器，所以可以直接作为sort函数的参数,排序默认是按照pair的第一个元素进行比较的。如果第一个元素相等，则会比较第二个元素。

法二：使用map(不是unordered_map),它能够实现自主排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        map<int, int, greater<int>> mp; //由大到小,看第一个int
        int n = score.size();
        string rankTop[3] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        for (int i = 0; i < n; i++) {
            mp[score[i]] = i;
        }
        vector<string> res(n);
        auto it = mp.begin(); // it是迭代器
        for (int i = 0; i < n; i++) {
            if (i < 3) {
                res[(*it).second] = rankTop[i];
            } else {
                res[(*it).second] = to_string(i + 1);
            }
            it++;
        }
        return res;
    }
};

法三：使用set,方法与使用map类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        set<pair<int, int>, greater<pair<int, int>>> s; //由大到小
        int n = score.size();
        string rankTop[3] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        for (int i = 0; i < n; i++) {
            s.emplace(score[i], i);
        }
        vector<string> res(n);
        auto it = s.begin();
        for (int i = 0; i < n; i++) {
            if (i < 3) {
                res[(*it).second] = rankTop[i];
            } else {
                res[(*it).second] = to_string(i + 1);
            }
            it++;
        }
        return res;
    }
};

值得注意的是:1.set不存在类似s[i]的表示形式

2.向set中加入元素应该使用emplace而非empalce_back

3.元素形式为pair时，定义应该为set<pair<int, int>, greater<pair<int, int>>> s，这里的排序写法不是greater!greater<int>表示按照键值进行降序排序，只有map、vector这种元素对应键值才是固定的，set则随时改变元素的位置，在元素为int类型时greater没有问题，但在pair类型时，会出错。

在这种情况下，我们需要使用greater<pair<int, int>>而不是greater<int>，因为我们想要按照分数降序排列，并且在分数相同时，按照索引升序排列。使用greater<pair<int, int>>可以确保首先按照分数降序排列，然后按照索引升序排列。

鸽巢原理：539法二。由鸽巢原理可知，如果 timePoints 的长度超过 1440，那么必然会有两个相同的时间，此时可以直接返回 0.

6-2.正则表达式：537

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string complexNumberMultiply(string num1, string num2) {
    // 定义正则表达式，用于匹配"+"和"i"
    regex re("\\+|i"); 

    // 用正则表达式对复数字符串进行分割，存储到vector中
    vector<string> complex1(sregex_token_iterator(num1.begin(), num1.end(), re, -1), std::sregex_token_iterator());
    vector<string> complex2(sregex_token_iterator(num2.begin(), num2.end(), re, -1), std::sregex_token_iterator());

    // 将分割后的字符串转换为整数部分和虚数部分
    int real1 = stoi(complex1[0]);
    int imag1 = stoi(complex1[1]);
    int real2 = stoi(complex2[0]);
    int imag2 = stoi(complex2[1]);

    // 计算两个复数的乘积
    return to_string(real1 * real2 - imag1 * imag2) + "+" + to_string(real1 * imag2 + imag1 * real2) + "i";
}

关于正则

1.regex:regex是C++标准库中用于处理正则表达式的类。它允许你使用正则表达式来进行字符串的匹配、搜索和替换操作。通过使用regex类，你可以在C++中执行与正则表达式相关的操作，例如查找模式匹配、提取部分字符串、替换文本等。需要头文件<regex>

2.sregex_token_iterator:sregex_token_iterator是C++标准库中用于在字符串上执行正则表达式分词操作的迭代器。它允许你在字符串中使用正则表达式来进行分词，从而将字符串分割为符合特定模式的子字符串。在上面的代码中，sregex_token_iterator来将复数字符串根据正则表达式分割为整数部分和虚数部分。

语法：sregex_token_iterator(起始位置，终止位置，正则, 返回的匹配类型（-1是返回未匹配的部分，即分隔操作）)。

会返回一个迭代器的首地址，std::sregex_token_iterator()会返回一个end。vector用这两个迭代器构造得到符合匹配的序列

3.正则匹配：正则表达式-菜鸟教程 - Theseus‘Ship - 博客园

C++ 正则表达式 - Chen沉尘 - 博客园

[笔记]c++基础实践《二》regex正则表达式_51CTO博客_c++ 正则表达式

4."\\+|i" 这个正则表达式中，\\+ 匹配加号 “+”，| 表示或，i 匹配字符 “i”。因此，这个正则表达式可以用于匹配复数字符串中的加号和虚数单位 “i”。

"(-?\\d+)/(\\d+)([+-])(-?\\d+)/(\\d+)"表示两个分数相加。

  • -?：表示匹配一个可选的减号（负号）。- 表示减号，? 表示前面的字符（这里是减号）在文本中可以出现 0 次或 1 次。
  • \\d+：表示匹配一个或多个数字。\\d 表示一个数字，+ 表示前面的元素（这里是数字）可以出现一次或多次。(\\.用来表示小数点)
  • [+-] 是一个正则表达式模式，用于匹配加号(+)或减号(-)。在正则表达式中，方括号 [] 用于表示一个字符集，其中列出的字符之一都可以匹配成功。因此，[+-] 表示匹配一个加号或减号。

5.smatch:smatch 是 C++ 标准库中的一种数据结构，用于存储正则表达式匹配的结果。它是 std::match_results 类型的别名，用于保存正则表达式匹配的结果和子匹配的位置信息。当使用正则表达式进行匹配时，匹配结果会被存储在 smatch 对象中，可以通过索引或迭代器来访问匹配的子字符串。在T592中，使用 smatch 对象来存储正则表达式匹配的结果，并从中提取分数的分子、分母以及操作符等信息。

matches[5].str() 表示从 smatch 对象中获取第 5 个匹配的子字符串，并将其作为 std::string 类型返回。在这种情况下，matches[5] 用于访问正则表达式匹配中的第 5 个捕获组，即第 5 个括号内匹配的内容。在T592中，matches[5].str() 用于获取第 5 个捕获组的字符串表示形式(\\d+)，这个捕获组对应于分数的分母。

matches.prefix().str() 表示从 smatch 对象中获取匹配的子字符串之前的部分，并将其作为 std::string 类型返回。在这种情况下，matches.prefix() 用于获取匹配子字符串之前的部分，然后通过 str() 方法将其转换为字符串表示形式。

matches.suffix().str()则表示之后的那部分。

6.用括号将正则表达式分成多组

在正则表达式中使用括号可以将匹配的部分分组，这样做有几个好处：

  • 提取子匹配：括号可以将匹配的部分分成多个组，这样可以方便地从整个匹配中提取出我们感兴趣的部分。在这个例子中，括号将分数的分子、分母以及操作符分成了多个组，方便后续的处理。

  • 方便后续处理：分组可以让我们更方便地对匹配到的内容进行后续处理，比如在这个例子中，可以方便地提取出分数的分子和分母，然后进行加减法运算。

  • 捕获匹配信息：分组可以捕获匹配的信息，方便后续的引用。在这个例子中，我们可以使用 matches[1]、matches[2]、matches[3] 等来引用不同的匹配组。

因此，使用括号将正则表达式的部分分成多个组可以使代码更清晰、更易于理解，并且方便后续的处理和提取。

7.regex_search:regex_search(expression, matches, pattern)用于在字符串 expression 中搜索满足正则表达式模式 pattern 的部分，并将匹配的结果存储在 matches 对象中，以便后续的处理和提取。

8.regex_match:regex_match(string code, regex pattern)用于检查字符串是否与给定的正则表达式模式匹配。在这种情况下，它会尝试使用给定的正则表达式模式pattern来匹配输入的代码字符串code，并返回bool值。

9.相关学习网站：Road 2 Coding

正则表达式测试网站：regex101

在对性能敏感的程序中尽量避免使用正则表达式，尽量使用更加高效、更加简单的字符串匹配方案来提高程序性能。在C++中，正则表达式使用ECMAScript语法作为默认语法。这意味着它使用类似于JavaScript和Python的正则表达式语法。但C++的正则表达式与其他语言的正则表达式相比，缺少了独占模式，只有贪婪模式和非贪婪模式(懒惰模式)，这使得匹配所消耗的时间更长。

ECMAScript语法：Modern C++ 学习笔记——正则表达式

藏在正则表达式中的陷阱—知乎

正则表达式引起的性能下降—博客园

正则规则汇总

6-3.分数加减运算：592

法一：模拟，遍历整个字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string fractionAddition(string expression) {
        int n = expression.size(), index = 0;
        long long x = 0, y = 1;
        while (index < n) {
            //分子
            long long x1 = 0, sign = 1; // x1记录当前数字,sign记录正负号
            if (expression[index] == '-' || expression[index] == '+') {
                sign = expression[index] == '-' ? -1 : 1;
                index++;
            }
            while (index < n && isdigit(expression[index])) { // index<n别忘了
                x1 = x1 * 10 + expression[index] - '0';       //更新x1
                index++;
            }
            //遇到“/”
            x1 *= sign; //最后把符号带上
            index++;

            //分母.再次遇到+/-时则结束
            long long y1 = 0; //分母不可能有符号，所以无需sign
            while (index < n && isdigit(expression[index])) {
                y1 = y1 * 10 + expression[index] - '0';
                index++;
            }

            //更新当前数字(再次遇到“+/-”时),x/y+=x1/y1
            x = x * y1 + x1 * y;
            y *= y1;
        }
        if (x == 0) {
            return "0/1";
        }
        long long g = gcd(abs(x), y); //获取最大公约数，用来化简分数
        return to_string(x / g) + "/" + to_string(y / g);
    }
};

法二：正则匹配,该解法的时间复杂度为$ O(n^2)$，空间复杂度为 $O(1)$,但法一时间复杂度仅为$O(n+log⁡C)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <regex>
#include <string>

class Solution {
public:
    string performOperation(int num1, int den1, int num2, int den2, char op) {
        int numerator, denominator;
        if (op == '+') {
            numerator = num1 * den2 + num2 * den1;
        } else {
            numerator = num1 * den2 - num2 * den1;
        }
        denominator = den1 * den2;
        return toLowestTerms(numerator, denominator);
    }

    string toLowestTerms(int numerator, int denominator) {
        int divisor = gcd(abs(numerator), abs(denominator));
        return to_string(numerator / divisor) + "/" +
               to_string(denominator / divisor);
    }

    string fractionAddition(string expression) {
        regex pattern("(-?\\d+)/(\\d+)([+-])(-?\\d+)/(\\d+)");
        smatch matches;
        while (regex_search(expression, matches, pattern)) {
            int num1 = std::stoi(matches[1].str());
            int den1 = std::stoi(matches[2].str());
            int num2 = std::stoi(matches[4].str());
            int den2 = std::stoi(matches[5].str());
            char op = matches[3].str()[0];

            expression = matches.prefix().str() +
                         performOperation(num1, den1, num2, den2, op) +
                         matches.suffix().str();
        }
        return expression;
    }
};

关于最大公约数gcd和最小公倍数lcm:

(Greatest Common Divisor、Least Common Multiple)

需要的头文件为<numeric>

6-4.分数到小数(分数乘除运算)：166

两个整数相除，结果一定是有理数，一定有循环。使用了哈希表存储竖式模拟过程中出现过的余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long numeratorLong = numerator;
        long denominatorLong = denominator;
        if (numeratorLong % denominatorLong == 0) {
            return to_string(numeratorLong / denominatorLong);
        }

        string ans;
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            ans.push_back('-');
        }

        // 整数部分
        numeratorLong = abs(numeratorLong);
        denominatorLong = abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        ans += to_string(integerPart);
        ans.push_back('.');

        // 小数部分
        string fractionPart;
        unordered_map<long, int> remainderIndexMap;
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexMap.count(remainder)) {
            remainderIndexMap[remainder] = index;
            remainder *= 10;
            fractionPart += to_string(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // 有循环节
            int insertIndex = remainderIndexMap[remainder];
            fractionPart = fractionPart.substr(0,insertIndex) + '(' + fractionPart.substr(insertIndex);
            fractionPart.push_back(')');
        }
        ans += fractionPart;

        return ans;
    }
};

6-5.求解方程：640

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    string solveEquation(string equation) {
        int index = 0, n = equation.size(), sign1 = 1; // sign1记录等式右边系数
        int factor = 0, val = 0; //记录变量的系数，常量值
        while (index < n) {
            if (equation[index] == '=') {
                sign1 = -1; //等式右边默认系数为负
                index++;
                continue;
            }
            int sign2 = sign1, number = 0;
            bool valid = false; //记录number是否有效
            if (equation[index] == '-' ||
                equation[index] == '+') { //去掉前面的符号
                sign2 = (equation[index] == '-') ? -sign1 : sign1;
                index++;
            }
            while (index < n && isdigit(equation[index])) {
                number = number * 10 + equation[index] - '0';
                index++;
                valid = true;
            }
            if (index < n && equation[index] == 'x') { //变量
                factor += valid ? sign2 * number : sign2;
                index++;
            } else { //数值
                val += sign2 * number;
            }
        }

        if (!factor) {  //factor * x + val = 0
            return val == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + to_string(-val / factor);
    }
};

6-6.外观数列：38

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string countAndSay(int n) {
        string prev = "1"; //记录下前一个字符串是什么，默认为第一个字符串"1"
        for (int i = 2; i <= n; i++) {
            string curr = "";
            int start = 0, pos = 0;//双指针
            while (pos < prev.size()) {
                while (pos < prev.size() && prev[pos] == prev[start]) {
                    pos++;
                }
                curr += to_string(pos - start) + prev[start];
                start = pos; //更新start
            }
            prev = curr; //更新prev为下一个字符串
        }
        return prev;
    }
};

6-6.自定义字符串转换整数：8

法一：依次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int strToInt(string str) {
        if (str.empty()) return 0;
        int index = 0, n = str.size(), sign = 1, res = 0;
        // 处理前置空格
        while (index < n && str[index] == ' ') {
            ++index;
        }
        // 处理符号，应该继续向后，因为+-12的结果应为0
        if (index < n && (str[index] == '+' || str[index] == '-')) {
            sign = str[index++] == '+' ? 1 : -1;
        }
        // 处理数字
        while (index < n && isdigit(str[index])) {
            int digit = str[index++] - '0';
            // 判断是否溢出
            if (res > (INT_MAX - digit) / 10) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            res = res * 10 + digit;
        }
        return res * sign;
    }
};

本题关键：处理整数溢出的情况，原题：如果整数数超过 32 位有符号整数范围 $[−2^{31}, 2^{31} − 1]$ ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 $2^{31}$ 的整数应该被固定为 $2^{31}$ ，大于 $2^{31}− 1$ 的整数应该被固定为 $2^{31}− 1 $。

法二：自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Automaton {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start", "signed", "in_number", "end"}},
        {"signed", {"end", "end", "in_number", "end"}},
        {"in_number", {"end", "end", "in_number", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    int get_col(char c) {
        if (isspace(c)) return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
public:
    int sign = 1;
    long long ans = 0;

    void get(char c) {
        state = table[state][get_col(c)];
        if (state == "in_number") {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        }
        else if (state == "signed")
            sign = c == '+' ? 1 : -1;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        Automaton automaton;
        for (char c : str)
            automaton.get(c);
        return automaton.sign * automaton.ans;
    }
};

关于自动机

在C++中，自动机通常指的是有限状态自动机（Finite State Machine，FSM），它是一种抽象的数学模型，用于描述系统的状态及状态之间的转移。

一个简单的有限状态自动机由以下几部分组成：

  • 一组状态：描述系统可能处于的状态。
  • 一组转移：描述状态之间的转移条件。
  • 初始状态：描述系统的初始状态。
  • 终止状态：描述系统的结束状态。

在C++中，我们可以使用类和枚举类型来实现有限状态自动机。以下是一个简单的示例，演示了一个有限状态自动机，用于模拟一个简单的灯的状态变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>

// 枚举类型表示灯的状态
enum class LightState {
    OFF,
    ON,
    DIM
};

class LightStateMachine {
private:
    LightState state;

public:
    LightStateMachine() : state(LightState::OFF) {}

    void transition() {
        switch (state) {
            case LightState::OFF:
                state = LightState::ON;
                break;
            case LightState::ON:
                state = LightState::DIM;
                break;
            case LightState::DIM:
                state = LightState::OFF;
                break;
        }
    }

    LightState getState() {
        return state;
    }
};

int main() {
    LightStateMachine light;

    std::cout << "Initial state: " << static_cast<int>(light.getState()) << std::endl;

    light.transition();
    std::cout << "State after transition: " << static_cast<int>(light.getState()) << std::endl;

    light.transition();
    std::cout << "State after transition: " << static_cast<int>(light.getState()) << std::endl;

    return 0;
}

在上面的示例中，我们定义了一个简单的有限状态自动机 LightStateMachine，用于模拟灯的状态变化。通过调用 transition 方法，状态机会根据当前状态进行转移，并可以通过 getState 方法获取当前状态。

6-6.整数转罗马数字：12

法一：模拟

注意，这里不能用unordered_map，因为其遍历的时候是乱序的，应该用能设置排列规则的map，用greater<int>保证由大到小遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <map>
#include <string>

class Solution {
private:
    const map<int, string, greater<int>> valueSymbols = {
        {1000, "M"},
        {900,  "CM"},
        {500,  "D"},
        {400,  "CD"},
        {100,  "C"},
        {90,   "XC"},
        {50,   "L"},
        {40,   "XL"},
        {10,   "X"},
        {9,    "IX"},
        {5,    "V"},
        {4,    "IV"},
        {1,    "I"},
    };
//使用了greater<int>才能保证遍历顺序是按照当前1000->500->...
public:
    string intToRoman(int num) {
        string roman;
        for (const auto& [value, symbol] : valueSymbols) { //注意auto前面这里需要加上const
            while (num >= value) {
                num -= value;
                roman += symbol;
            }
            if (num == 0) {
                break;
            }
        }
        return roman;
    }
};


也可以直接使用数组，其中每个元素均为pair类型。遍历数组的顺序并不是乱序。pair数组除了第一行的定义以外，其他代码几乎没有区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const pair<int, string> valueSymbols[] = {
    {1000, "M"},
    {900,  "CM"},
    {500,  "D"},
    {400,  "CD"},
    {100,  "C"},
    {90,   "XC"},
    {50,   "L"},
    {40,   "XL"},
    {10,   "X"},
    {9,    "IX"},
    {5,    "V"},
    {4,    "IV"},
    {1,    "I"},
};

class Solution {
public:
    string intToRoman(int num) {
        string roman;
        for (const auto &[value, symbol] : valueSymbols) {
            while (num >= value) {
                num -= value;
                roman += symbol;
            }
            if (num == 0) {
                break;
            }
        }
        return roman;
    }
};

法二：硬编码数字

1
2
3
4
5
6
7
8
9
10
11
12
const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[]      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

class Solution {
public:
    string intToRoman(int num) {
        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }
};

6-7.比较版本号：165

注意其中细节即可，双指针法，尽可能简化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int compareVersion(string version1, string version2) {
        int pos1 = 0, pos2 = 0;
        int n1 = version1.length(), n2 = version2.length();
        while (pos1 < n1 || pos2 < n2) { //用或，需要把两个都遍历完
            long int v1 = 0, v2 = 0; //版本号可能是"1.2147483647"
            while (pos1 < n1 && version1[pos1] != '.') {
                v1 = v1 * 10 + version1[pos1++] - '0';
            }
            while (pos2 < n2 && version2[pos2] != '.') {
                v2 = v2 * 10 + version2[pos2++] - '0';
            }
            if (v1 != v2) {
                return v1 > v2 ? 1 : -1;
            }
            pos1++;
            pos2++;
        }
        return 0;
    }
};

stoi(stringVar)中，stringVar不能为空。

6-8.神奇字符串：481

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int magicalString(int n) {
        string s = "\1\2\2"; //需要用反斜杠
        // 值就是 1,2,2，这样就可以直接用 s[i] 当作个数
        for (int i = 2; s.length() < n; ++i) {
            s += string(s[i], s.back() ^ 3);
            // 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换
        }
        return count(s.begin(), s.begin() + n, 1);
    }
};

  1. string s = "\1\2\2";和string s = "122";的区别:在C++中，字符串字面值中的转义序列是以反斜杠（\）开头的字符序列。"\1\2\2" 和 "122" 的区别在于转义序列的使用。"\1\2\2"：这个字符串包含了转义序列 \1、\2 和 \2。这些是八进制转义序列，代表特定的ASCII字符。具体而言，\1 对应ASCII值1，\2 对应ASCII值2。因此，这个字符串实际上是包含了三个字符，分别是1、2和2。"122"这个字符串没有使用八进制转义序列，它只包含了三个字符，分别是’1’、’2’和’2’。前者的s[i]可以直接用来当做个数。

  2. s += string(s[i], s.back()^3)：string(int count,char value);这是表示s加上一个包含value字符，且长度为count的字符串。比如s+=string('\2', 1)就是s+="11",常规写法是string(2, '1');

  3. s.back()^3:s.back()就是字符串s的最后一个字符。^3用于实现1与2的不断切换，1^3=2, 2^3=1.(二进制运算)

  4. count(s.begin(), s.begin()+n, 1):计数特定区间内有多少个值为1的字符。模板count(T.begin(),T.end(),value)。

现在不用反斜杠：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int magicalString(int n) {
        string s = "122"; //不用反斜杠
        // 这样就不可以直接用 s[i] 当作个数
        for (int i = 2; s.length() < n; ++i) {
            s += string(s[i]-'0', (s.back()-'0') ^ 3 +'0');
            // 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换
        }
        return count(s.begin(), s.begin() + n, '1');
    }
};