常见“栈“相关题目

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏： 优选算法专题

目录

1047.删除字符串中的所有相邻重复项

844.比较含退格的字符串

227.基本计算器 II

394.字符串解码

946.验证栈序列

1047.删除字符串中的所有相邻重复项

题目：

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= s.length <= 105
2. s 仅由小写英文字母组成。

思路：这个题目有点类似消消乐这个游戏，这种我们一般都是采用栈的方式来实现。

直接使用栈的方式：遍历字符串，如果栈不为空，且栈顶的元素与当前字符串的元素的值相同，就出栈，否则就进栈。直至遍历完字符串，然后再遍历栈拿到最终的字符序列，最后只需逆置即可。

上面的方式虽然非常简单，但是需要遍历栈拿到字符序列，最后还得去逆置，比较麻烦，我们可以尝试去模拟栈的思想来解决。创建一个StringBuilder对象，当该对象的字符数不为null，且最后一个字符与当前字符串中的元素的值相等时，就删除最后一个字符，否则就加入该对象。最后遍历完成之后，就可以直接返回了。

代码实现：

直接使用栈：

class Solution {
    // 直接使用栈
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 栈不为空且栈顶元素与当前字符串的元素的值相等，就出栈
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        return builder.reverse().toString();
    }
}

模拟栈：

class Solution {
    // 模拟栈的方式
    public String removeDuplicates(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 与上述栈的处理方式相同
            if (builder.length() != 0 && builder.charAt(builder.length()-1) == c) {
                builder.deleteCharAt(builder.length()-1);
            } else {
                builder.append(c);
            }
        }
        return builder.toString();
    }
}

注意：StringBuilder (StringBuffer) 的 capacity方法 与 length方法 的含义不一样。capacity方法是获取其底层的字符数组的大小（不是有效的元素个数，而是总大小），length方法是获取其字符数组的有效长度。 

844.比较含退格的字符串

题目：

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

思路：本题也是一个简单的模拟题。遍历字符串，遇到 '#'，就删除前面的字符即可，最终只需要判断两个字符串经过上述处理之后的结果是否是一致的。

代码实现：

class Solution {
    public boolean backspaceCompare(String s, String t) {
        StringBuilder ss = new StringBuilder();
        StringBuilder tt = new StringBuilder();
        for (int i = 0, j = 0; i < s.length() || j < t.length(); i++, j++) {
            if (i < s.length()) {
                // 遇到 '#' 且 StringBuilder 对象不为空，就出栈
                if (s.charAt(i) == '#') {
                    if (ss.length() != 0) {
                        ss.deleteCharAt(ss.length()-1);
                    }
                } else {
                    ss.append(s.charAt(i));
                }
            }
            
            if (j < t.length()) {
                // 遇到 '#' 且 StringBuilder 对象不为空，就出栈
                if (t.charAt(j) == '#') {
                    if (tt.length() != 0) {
                        tt.deleteCharAt(tt.length()-1);
                    }
                } else {
                    tt.append(t.charAt(j));
                }
            }
        }
        return ss.toString().equals(tt.toString());
    }
}

注意：StringBuilder(StringBuffer) 的 equals 方法并未重写，而是直接继承的Object类的equals方法，比较的是对象的内存地址；而String的equals方法是重写之后的，比较的对象的值。因此这里在比较时，需要先使用 toString方法转换为字符串，再去比较。

227.基本计算器 II

题目：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

• 1 <= s.length <= 3 * 10^5
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

思路：题目就是让我们计算出一段字符串序列的最终值，而这个字符串序列中包含了 +、-、*、/、空格 与 数字。由于在计算字符串序列的值时，乘除运算符的优先级是高于加减的，因此我们可以先将乘除的运算全部先计算出来，最后再去计算出加减的值。那我们就可以先遍历字符串，如果遇到了空格可以直接跳过，如果遇到了数字字符，就拿到完整的数字（可能不是一位数），然后根据前者的运算符是啥，来决定当前数据做什么处理，如果遇到了运算符，就直接记录下来即可。

代码实现：

class Solution {
    public int calculate(String s) {
        int n = s.length(), i = 0;
        char[] strs = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        char op = '+'; // 初始化为'+'
        while (i < n) {
            // 排除空格的情况
            while (i < n && strs[i] == ' ') { // 避免越界
                i++;
            }
            if (i == n) {
                break;
            }
            // 处理数字
            if (i < n && strs[i] >= '0' && strs[i] <= '9') {
                // 先拿到完整的数字
                int num = 0;
                while (i < n && strs[i] >= '0' && strs[i] <= '9') {
                    num = num * 10 + (strs[i] - '0');
                    i++;
                }
                // 根据运算符的情况，将不同情况的数据入栈
                if (op == '+') { // 加上数据
                    stack.push(num);
                } else if (op == '-') { // 减去数据
                    stack.push(-num);
                } else if (op == '*') { // 让栈顶的数据乘上该数据
                    stack.push(stack.pop() * num);
                } else { // 让栈顶的数据除去该数据
                    stack.push(stack.pop() / num);
                }
                // 处理完上述不需要 i++，因为上述刚好将i+1的位置确认为非数字，但未处理
            } else {
                // 处理运算符
                op = strs[i];
                i++;
            }
        }
        // 将栈中所有元素相加即可
        int ret = 0;
        while (!stack.isEmpty()) {
            ret += stack.pop();
        }
        return ret;
    }
}

394.字符串解码

题目：

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

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

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

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

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300] 

思路：本题和表达式求值的思路是类似的，都是先计算出优先级较高的。而这里是需要我们先将括号内的字符串解析出来，然后再去拼接出最终的字符串。内嵌的字符串的优先级是最高的，也是最先需要解析出来的。

代码实现：

class Solution {
    public String decodeString(String s) {
        // 创建一个数字栈、一个字符串栈
        Stack<String> s_stack = new Stack<>();
        Stack<Integer> n_stack = new Stack<>();
        s_stack.push(""); // 避免纯字符前缀无法添加到栈顶元素的末尾
        int n = s.length(), i = 0;
        char[] strs = s.toCharArray();
        while (i < n) {
            if (strs[i] >= '0' && strs[i] <= '9') { // 数字
                int num = 0;
                while (strs[i] >= '0' && strs[i] <= '9') { // 可能不止一位数
                    num = num * 10 + (strs[i] - '0');
                    i++;
                }
                n_stack.push(num); // 数字入栈
            } else if (strs[i] == '[') { // 左括号
                // 字符串入栈
                i++;
                StringBuilder builder = new StringBuilder();
                // 只需要加入字母，避免右括号 与 数字
                while (strs[i] != ']' && strs[i] <= '0' && strs[i] >= '9') {
                    builder.append(strs[i++]);
                }
                s_stack.push(builder.toString());
            } else if (strs[i] == ']') { // 右括号
                // 字符串栈 出栈，数字栈 出栈
                StringBuilder builder = new StringBuilder(s_stack.pop());
                StringBuilder tmp = new StringBuilder(builder);
                int k = n_stack.pop();
                for (int j = 0; j < k-1; j++) {
                    tmp.append(builder);
                }
                // 添加到栈顶元素的末尾
                builder = new StringBuilder(s_stack.pop());
                s_stack.push(builder.append(tmp).toString());
                i++;
            } else { // 纯字符串
                // 拿到字符串
                StringBuilder tmp = new StringBuilder();
                while (i < n && strs[i] >= 'a' && strs[i] <= 'z') {
                    tmp.append(strs[i++]);
                }
                // 直接添加到栈顶元素的末尾
                StringBuilder builder = new StringBuilder(s_stack.pop());
                builder.append(tmp);
                s_stack.push(builder.toString());
            }
        }
        return s_stack.pop().toString();
    }
}

946.验证栈序列

题目：

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed 的所有元素 互不相同
• popped.length == pushed.length
• popped 是 pushed 的一个排列

思路：只需要将push序列一直进栈，并同时判断栈顶的元素是否与指向popped序列的指针值是否一致，如果一致的话，就一致出栈，直至栈为空，如果不一致就一直进栈。重复上述过程，直至最终的栈为空，或者指向popped序列的值为空，说明出栈序列是正确的，反之，则是错误的。

代码实现：

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0, n = popped.length;
        while (i < n) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
            i++;
        }
        return stack.isEmpty();
    }
}

好啦！本期 常见“栈“相关题目 的刷题之旅 就到此结束啦！我们下一期再一起学习吧！