栈：压栈匹配

睡不醒的鲤鱼 2021-08-02 每日一题 LeetCode

# 0032. 最长有效括号 (opens new window)

题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解析

一个合法的括号序列需要满足以下两个条件：

任意前缀中左括号的数量 $\ge$ 右括号的数量；
左右括号数量相等。

因此可以根据首次不合法的右括号（右括号数量首次大于左括号数量的位置）将原字符串划分成多段，可以看出，最长有效括号一定在段内产生；之后在每一段内找到所有合法括号序列，求出最大值即可。具体算法如下：

遇到左括号，将下标入栈；
遇到右括号：
1. 如果栈不空，将栈顶元素出栈，与当前右括号匹配：
  1. 出栈后栈不空，则栈顶元素的下一个位置开始即为合法序列；
  2. 出栈后栈为空，则当前段起始点开始都为合法序列；
2. 如果栈为空，说明此时右括号为首次不合法的右括号，更新段起始位置。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int ans = 0;
        for (int i = 0, start = -1; i < s.length(); i++) {
            if (s[i] == '(') stk.push(i);
            else {
                if (!stk.empty()) {
                    stk.pop();
                    if (!stk.empty()) {
                        ans = max(ans, i - stk.top());
                    } else {
                        ans = max(ans, i - start);
                    }
                } else {
                    start = 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

# 0071. 简化路径 (opens new window)

题目

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的规范路径必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的规范路径。

解析

将原始路径按 / 进行分割，当遇到路径名时入栈，遇到 .. 时出栈，最后将栈中元素拼接即可。

代码

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> stk;
        stringstream ss(path);
        string item;
        while (getline(ss, item, '/')) {
            if (item == "..") {
                if (!stk.empty()) stk.pop();
            } else if (item != "." && item != "") {
                stk.push(item);
            }
        }
        string ans;
        while (!stk.empty()) {
            ans = "/" + stk.top() + ans;
            stk.pop();
        }
        return ans.empty() ? "/" : ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 0341. 扁平化嵌套列表迭代器 (opens new window)

题目

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
int next() 返回嵌套列表的下一个整数。
boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

1
2
3
4
5

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

解析

将原始嵌套列表逆序入栈，在出栈过程中进行类型判断，若为嵌套列表，则将其中元素拆分后重新入栈。

代码

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
    stack<NestedInteger> stk;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stk.push(nestedList[i]);
        }
    }
    
    int next() {
        int ans = stk.top().getInteger();
        stk.pop();
        return ans;
    }
    
    bool hasNext() {
        while (!stk.empty()) {
            NestedInteger cur = stk.top();
            if (cur.isInteger()) {
                return true;
            }
            stk.pop();
            for (int i = cur.getList().size() - 1; i >= 0; i--) {
                stk.push(cur.getList()[i]);
            }
        }
        return false;
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

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

# 0385. 迷你语法分析器 (opens new window)

题目

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

列表中的每个元素只可能是整数或整数嵌套列表

提示：你可以假定这些字符串都是格式良好的：

字符串非空
字符串不包含空格
字符串只包含数字0-9、[、-、,、]

解析

栈+双指针，栈中依次存储由外到内的 NestedInteger，每次处理完一个 NestedInteger，将栈顶元素 pop 并加入新的栈顶元素中，遍历结束，栈中只存在一个 NestedInteger 就是最终的返回结果。

代码

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s.find("[") != 0) {
            return NestedInteger(stoi(s));
        }
        stack<NestedInteger> stk;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s[i];
            if (ch == '[') {
                stk.push(NestedInteger());
                start = i + 1;
            } else if (ch == ']' || ch == ',') {
                if (start < i) {
                    int num = stoi(s.substr(start, i - start));
                    stk.top().add(NestedInteger(num));
                }
                if (ch == ']' && stk.size() > 1) {
                    NestedInteger cur = stk.top(); stk.pop();
                    stk.top().add(cur);
                }
                start = i + 1;
            }
        }
        return stk.top();
    }
};

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

# 0388. 文件的最长绝对路径 (opens new window)

题目

在文本格式中，如下所示(⟶表示制表符)：

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext

1
2
3
4
5
6
7

如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。

文件系统中的每个文件和文件夹都有一个唯一的绝对路径，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的绝对路径是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中名称和扩展名由字母、数字和/或空格组成。

给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中指向文件的最长绝对路径的长度。如果系统中没有文件，返回 0。

解析

使用一个栈记录每条路径的累计长度，遇到路径结尾则出栈至上级路径，遍历结束即得到最长绝对路径的长度。

代码

class Solution {
public:
    int lengthLongestPath(string input) {
        stack<int> stk;
        stk.push(0);
        stringstream ss(input);
        string item;
        int ans = 0;
        while (getline(ss, item, '\n')) {
            int level = item.rfind('\t') + 1;

            // 找到上一级路径
            while (level + 1 < stk.size()) {
                stk.pop();
            }
            int len = stk.top() + item.length() - level + 1;
            stk.push(len);

            // 路径结尾
            if (item.find('.') != -1) {
                ans = max(ans, len - 1);
            }
        }
        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
26

# 0394. 字符串解码 (opens new window)

题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

解析

使用两个栈分别存储数字和字符串，遍历原始字符串，分情况讨论：

数字：截取完整数组 push 到数字 stack；
字符：拼接到当前字符串上；
[：说明开始一个新的字符串，将当前字符串入栈后重置；
]：将当前字符串重复指定次数后与前一个字符串拼接。

代码

class Solution {
public:
    string decodeString(string s) {
        stack<int> numStk;
        stack<string> strStk;
        string cur = "";
        int idx = 0;
        while (idx < s.length()) {
            if (isdigit(s[idx])) {
                int num = 0;
                while (isdigit(s[idx])) {
                    num = num * 10 + (s[idx] - '0');
                    idx++;
                }
                numStk.push(num);
            } else if (s[idx] == '[') {
                strStk.push(cur);
                cur = "";
                idx++;
            } else if (s[idx] == ']') {
                string tmp = strStk.top(); strStk.pop();
                int time = numStk.top(); numStk.pop();
                for (int i = 0; i < time; i++) {
                    tmp += cur;
                }
                cur = tmp;
                idx++;
            } else {
                cur += s[idx++];
            }
        }
        return cur;
    }
};

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

栈：表达式计算栈：单调栈

鲤鱼笔记

Choose mode