1.用栈访问最后若干元素

1
stack.push_back(move(name));

在这段代码中，move(name) 使用了 C++ 中的 std::move 函数。std::move 是一个用于将对象转换为右值引用的函数，它允许将对象的所有权转移给另一个对象，通常用于在移动语义中。在这段代码中，move(name) 可能是在将 name 对象的所有权转移给 stack 容器，这样做通常可以提高性能，避免不必要的拷贝操作。

1-1.文件的最长绝对路径：388

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:
    int lengthLongestPath(string input) {
        int ans = 0, pos = 0, n = input.length();
        stack<int>st;//用来记录每一段的长度
        // pos作为指针
        while (pos < n) {
            // 检测当前文件深度
            int depth = 1;
            //'\t'是一个符号，这里不是'\'和't'
            while (pos < n && input[pos] == '\t') {
                ++pos;
                ++depth;
            }
            // 统计当前文件名的长度
            int len = 0;
            bool isFile = false; // 记录是否为文件名而非目录名
            while (pos < n && input[pos] != '\n') {
                if (input[pos] == '.') {
                    isFile = true; // 因为此时后面必定是.ext
                }
                ++len;
                ++pos;
            }
            // 跳过换行符
            ++pos;

            // 遇到一次换行符之后的操作，对栈st进行操作
            while (st.size() >= depth) {
                st.pop();//回退一个文件层级
            }
            if (!st.empty()) {
                len += st.top() + 1;
            }
            if (isFile) {
                ans = max(ans, len);
            } else {
                st.emplace(len);
            }
        }
        return ans;
    }
};

stack.emplace(a) 的意思是在栈顶创建一个新的元素，并将参数 a 作为构造函数的参数，用于构造这个新的元素。push_back()，emplace_back()等最终调用的都是emplace_back()，性能并无区别。

关于emplace():emplace/emplace_back - 简书

2.栈与计算器

2-1.逆波兰表达式求值：150

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

1.如果遇到操作数，则将操作数入栈；

2.如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。[“13”,”5”,”/“]则表示13/5.

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:
    int isNumber(string& s) {
        return !(s == "+" || s == "-" || s == "*" || s == "/");
    }
    int evalRPN(vector<string>& tokens) {
        int n = tokens.size();
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            string& token = tokens[i];
            if (isNumber(token)) {
                stk.emplace(stoi(token));
            } else {
                //注意num2和num1的先后顺序
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                switch (token[0]) {
                    case '+':
                        stk.emplace(num1 + num2);
                        break;
                    case '-':
                        stk.emplace(num1 - num2);
                        break;
                    case '*':
                        stk.emplace(num1 * num2);
                        break;
                    case '/':
                        stk.emplace(num1 / num2);
                        break;
                }
            }
        }
        return stk.top();
    }
};

这里的emplace()也可以改用push()。为什么不是emplace_back()/push_back()的原因：emplace()/push()对应stack/queue，emplace_back()/push_back()对应list/vector(包括string这种特殊的字符数组)。

2-2.基本计算器II:227

本题不需要先将中缀表达式转为后缀表达式，因为全是正整数并且没有括号。该题本质上是用栈来处理，这里可以使用stack/vector。

1.使用stack:（易错点较多，需要注意）

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
class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        int n = s.size();
        int sign = '+'; // 记录数字前的符号，默认为正
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (isdigit(s[i])) {
                num = num * 10 + int(s[i] - '0'); // 小心溢出
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                // 记得考虑空格和末位的特殊情况
                switch (sign) { // 是sign而不是s[i],否则第一个数字无法存放
                case '+':
                    stk.push(num);
                    break;
                case '-':
                    stk.push(-num);
                    break;
                case '*':
                    stk.top() *= num;
                    break;
                case '/':
                    stk.top() /= num;
                    break;
                }
                // 处理完运算符以后，更新符号和数字
                sign = s[i];
                num = 0;
            }
        }
        int sum = 0;
        while (!stk.empty()) {
            sum += stk.top();
            stk.pop();
        }
        return sum;
    }
};

注意：num = num * 10 + s[i] - '0';会导致溢出，因为这时的运算顺序是先将num*10加上转为int的s[i]，之后再减去’0’转为的int值。而int(s[i]-'0')则能够避免溢出。

2.使用vector:

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
class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + int(s[i] - '0');
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;
                        break;
                    default:
                        stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};

通过对比可以看出，二者调用的方法略有不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
graph LR
    %%需要使用“ ”双引号将（）进行括起来，并给出一个命名，否则括号不可用
    subgraph vector
        A("push_back()")
        B["back()"] 
        C["accumulate()"]
    end

    subgraph stack
        D("push()")
        E["top()"]
        循环累加
    end

    A<-->D
    B<-->E
    C<-->循环累加

2-3.基本计算器：224（困难）

相比上一道题，其实就是多了括号和负数，本质是根据’+’分段存入栈中并计算。这类题如果采取先转为逆波兰表达式、再计算结果的方法，会使得代码非常庞杂。

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
class Solution {
public:
    int calculate(string s) {
        stack<int> stk; // 这里stk存储的不是操作数，而是符号ops
        stk.push(1);    // 默认为正号，所以提前存储1进去
        int n = s.length();
        int ans = 0, pos = 0;
        int sign = 1; // 默认为正数.sign值只能是+1或者-1
        while (pos < n) {
            switch (s[pos]) {
            case ' ':
                pos++;
                break;
            case '+':
                sign = stk.top();
                pos++;
                break;
            case '-':
                sign = -stk.top();
                pos++;
                break;
            case '(':
                stk.push(sign);
                pos++;
                break;
            case ')':
                stk.pop();
                pos++;
                break;
            default: // 是数字
                int num = 0;
                while (pos < n && isdigit(s[pos])) {
                    num = num * 10 + int(s[pos++] - '0');
                }
                ans += sign * num;
                break;
            }
        }
        return ans;
    }
};

进阶思考：存在乘除法，并且’+’可以用作一元运算符(例如"+1"和"+(2+3)"有效)

3.栈与括号匹配

3-1.有效的括号：20

难度不高

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
class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        int n = s.length();
        for (int pos = 0; pos < n; pos++) {
            if (s[pos] == '(' || s[pos] == '[' || s[pos] == '{') {
                stk.emplace(s[pos]);
            } else {
                if (stk.empty()) {
                    return false;
                }
                if (s[pos] == ')' && stk.top() != '(') {
                    return false;
                }
                if (s[pos] == ']' && stk.top() != '[') {
                    return false;
                }
                if (s[pos] == '}' && stk.top() != '{') {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }
};

3-2.函数的独占时间：636

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
class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n);
        stack<int> stk;
        int lastTimeStamp = 0; // 上一个数的时间戳
        for (auto& log : logs) {
            // 错误：数字可能不止一位
            // int id = log[0] - '0';
            // char StartOrEnd = log[3];
            // int timeStamp = log[(int)log.size() - 1];
            int id, timeStamp;
            char StartOrEnd[6];
            sscanf(log.c_str(), "%d:%[^:]:%d", &id, StartOrEnd, &timeStamp);

            // 本质是括号匹配
            if (StartOrEnd[0] == 's') {
                if (!stk.empty()) {
                    res[stk.top()] += timeStamp - lastTimeStamp;
                }
                // 存在栈里的都是start部分未被end匹配消除的部分对应的id
                stk.push(id);
                // 每次循环结束更新时间戳
                lastTimeStamp = timeStamp;
            } else {
                res[stk.top()] += timeStamp - lastTimeStamp + 1;
                stk.pop();
                // 为了统一时间戳标准，end的5相当于start的6.确保end-end正常
                lastTimeStamp = timeStamp + 1;
            }
        }
        return res;
    }
};

注：关于sscanf(log.c_str(), "%d:%[^:]:%d", &id, StartOrEnd, &timeStamp);，这里的租用类似于其他语言中的spilt()函数，用于将字符串根据’:’分割成不同的部分。sscanf()的功能类似于正则表达式的regex，胜在轻量级和高效，但是没有其强大。关于正则表达式regex，详见《2.1字符串篇(2)—-关于正则》。当字符串很长时，regex会涉及更多的内存释放和分配，并且需要更多的时间开销，可能导致超时或内存占用过高。

sscanf语法为：int sscanf(const char *str, const char *format, T* dividePart1ptr, T* dividePart2ptr, ...);，并将分割出的各个部分赋值到各个dividePart上。详细讲解：sscanf的用法

c_str()是一个用于将C++字符串转换为C风格的字符串（以null结尾的字符数组）的成员函数，它返回一个指向以null结尾的字符数组的指针，该字符数组包含了与C++字符串相对应的字符序列。比如：

1
const char *cStyleStringPointer = myString.c_str();

现在再来将之前sscanf代码转换为regex代码，如下：(在本题中会超时)

1
2
3
4
5
6
7
8
regex pattern("(\\d+):(\\w+):(\\d+)");
smatch matches;
if (regex_search(log, matches, pattern)) {
    id = stoi(matches[1]);
    string temp = matches[2];
    strcpy(StartOrEnd, temp.c_str());
    timeStamp = stoi(matches[3]);
}

现在又带来了新的知识点：是否可以将第6行代码写作StartEnd = temp.c_str();?答案是否定的，正如前面所说，c_str()返回的是以null结尾的字符数组的指针，而StartEnd只是个普通字符数组的指针，使用strcpy()则可以保证将temp中的内容复制到StartOrEnd中，并且最后有一个字符串结束符。

同理，第5和第6行也可以直接改为StartEnd = matches[2];，前提要求声明的是string StartEnd;，因为字符串也相当于是一个以null结尾的字符数组。

官方题解：

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
class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        stack<pair<int, int>> st; // {idx, 开始运行的时间}
        vector<int> res(n, 0);
        for (auto& log : logs) {
            char type[10];
            int idx, timestamp;
            sscanf(log.c_str(), "%d:%[^:]:%d", &idx, type, &timestamp);
            if (type[0] == 's') {
                if (!st.empty()) {
                    res[st.top().first] += timestamp - st.top().second;
                }
                st.emplace(idx, timestamp);
            } else {
                auto t = st.top();
                st.pop();
                res[t.first] += timestamp - t.second + 1;
                if (!st.empty()) {
                    st.top().second = timestamp + 1;
                }
            }
        }
        return res;
    }
};

3-3.标签验证器：591（困难）

法一：正则表达式匹配

错解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValid(string code) {
        // ECMAScript
        // std::regex
        // pattern("<([A-Z]{1,9}?>)[^<]*(<!\[CDATA\[(.+?)\]\]>)*[^<]*<\/\1");
        // leetcode需要将转义字符\再进行一次转义
        std::regex pattern(
            "<([A-Z]{1,9}?>)[^<]*(<!\\[CDATA\\[(.*?)\\]\\]>)*[^<]*<\\/\\1");
        if (std::regex_match(code, pattern)) {
            return true;
        } else {
            return false;
        }
    }
};

这样的代码存在缺陷，比如code="<A><A>/A></A></A>"或者"<HTML><DIV>/A></DIV></HTML>"或者"<A><B><C><D><E><F><G></G><H></H></F></E></D></C></B></A>"代码返回false，而实际应该返回true。如果改为regex_search()使用局部匹配而非完全匹配，则会导致"<HTMLQQQ><DIV>/A></DIV></HTML>"返回了true。

改进第一步：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isValid(string code) {
        std::regex pattern("<([A-Z]{1,9}?>)[^<]*(<!\\[CDATA\\[(.*?)\\]\\]>)*[^<]*<\\/\\1");
        while (std::regex_search(code, pattern) && code.length() > 1) {
            code = std::regex_replace(code, pattern, "#");
        }
        return code == "#";
    }
};

注意一点，"<DIV><UV><![CDATA[<GK><![CDATA[<![CDATA[OQA]]>]]></GK>]]></UV></DIV>"应该返回false!因为<![CDATA[CDATA_CONTENT]]>，CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]>之间的字符。因此还需要进一步改进。

改进第二步：(正解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValid(string code) {
        // 先处理掉cdata
        std::regex CDATApattern("<!\\[CDATA\\[(.*?)\\]\\]>");
        while (std::regex_search(code, CDATApattern)) {
            code = std::regex_replace(code, CDATApattern, "&");
        }
        //再解决可能嵌套的标签
        std::regex pattern("<([A-Z]{1,9}?>)[^<]*&*[^<]*<\\/\\1");
        while (std::regex_search(code, pattern)) {
            code = std::regex_replace(code, pattern, "#");
        }
        return code == "#";
    }
};

至此解题完毕，不过时空开销较大。

法二：栈+字符串遍历

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    bool isValid(string code) {
        int n = code.size();
        stack<string> tags;

        int i = 0;
        while (i < n) {
            if (code[i] == '<') {
                if (i == n - 1) {
                    return false;
                }
                if (code[i + 1] == '/') {
                    int j = code.find('>', i);
                    if (j == string::npos) {
                        return false;
                    }
                    string tagname = code.substr(i + 2, j - (i + 2));
                    if (tags.empty() || tags.top() != tagname) {
                        return false;
                    }
                    tags.pop();
                    i = j + 1;
                    if (tags.empty() && i != n) {
                        return false;
                    }
                } else if (code[i + 1] == '!') {
                    if (tags.empty()) {
                        return false;
                    }
                    string cdata = code.substr(i + 2, 7);
                    if (cdata != "[CDATA[") {
                        return false;
                    }
                    int j = code.find("]]>", i);
                    if (j == string::npos) {
                        return false;
                    }
                    i = j + 3;
                } else {
                    int j = code.find('>', i);
                    if (j == string::npos) {
                        return false;
                    }
                    string tagname = code.substr(i + 1, j - (i + 1));
                    if (tagname.size() < 1 || tagname.size() > 9) {
                        return false;
                    }
                    if (!all_of(tagname.begin(), tagname.end(),
                                [](unsigned char c) { return isupper(c); })) {
                        return false;
                    }
                    tags.push(move(tagname));
                    i = j + 1;
                }
            } else {
                if (tags.empty()) {
                    return false;
                }
                ++i;
            }
        }

        return tags.empty();
    }
};

3-4.最长有效括号：32（困难）

理解题意，有效括号子串形式为：1、”()()”;2、”(())”…其实就是满足3-1.第20题的那种字符串。

法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int ans = 0;
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) { // dp[0]必定为0
            // s[i]=='('时dp[i]必定为0
            if (s[i] == ')') {
                if (s[i - 1] == '(') { //"...()"型
                    dp[i] = (i >= 2 ? dp[i - 2] + 2 : 2);
                } else if (i > dp[i - 1] && s[i - dp[i - 1] - 1] == '(') { //"...))"型   
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] + 2 : 2);      
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

法二：栈

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 longestValidParentheses(string s) {
        int n = s.size();
        int ans = 0;
        stack<int> stk; // 存储的是最后一个无法匹配的括号对应的下标
        // 如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，
        // 这样就不满足提及的「最后一个没有被匹配的右括号的下标」，
        // 为了保持统一，我们在一开始的时候往栈中放入一个值为-1的元素。
        stk.push(-1);
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();//-1的作用体现在这里，一开始为')'时避免出错
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    ans = max(ans, i - stk.top());
                }
            }
        }
        return ans;
    }
};

法三：双计数器，近似于双指针（最优，不需要额外空间）

left统计左括号数，right统计右括号数。

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
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), left = 0, right = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                ans = max(ans, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0; // 重置，为下一次遍历做准备
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                ans = max(ans, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return ans;
    }
};

4.递归(了解)

4-1.迷你语法分析器：385

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
class Solution {
public:
    int index = 0;

    NestedInteger deserialize(string s) {
        if (s[index] == '[') {
            index++;
            NestedInteger ni;
            while (s[index] != ']') {
                ni.add(deserialize(s));
                if (s[index] == ',') {
                    index++;
                }
            }
            index++;
            return ni;
        } else {
            bool negative = false;
            if (s[index] == '-') {
                negative = true;
                index++;
            }
            int num = 0;
            while (index < s.size() && isdigit(s[index])) {
                num = num * 10 + s[index] - '0';
                index++;
            }
            if (negative) {
                num *= -1;
            }
            return NestedInteger(num);
        }
    }
};

341、394略。就是利用给的接口的方法解题。