面试经典150题——栈

1、有效的括号

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

1.3 解题代码

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if((n & 1) > 0){
            return false;
        }
        Stack<Character> stk = new Stack<>();
        for(int i = 0; i < n; ++i){
            char ch = s.charAt(i);
            if(stk.isEmpty()){
                stk.push(ch);
                continue;
            }
            char ch1 = stk.peek();
            if(ch == ')' && ch1 == '(' || ch == ']' && ch1 == '[' || ch == '}' && ch1 == '{'){
                stk.pop();
            } else if(ch == '(' || ch == '[' || ch == '{'){
                stk.push(ch);
            } else{
                return false;
            }
        }
    return stk.isEmpty();
    }
}

1.4 解题思路

1. 栈的经典题目括号匹配问题。
2. 如果栈为空则将括号压入数组中，如果栈顶元素和当前元素括号匹配，则出栈，否则入栈。
3. 最后遍历完毕若栈为空则返回false，否则返回true。

2、

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

在 Unix 风格的文件系统中规则如下：

• 一个点 ‘.’ 表示当前目录本身。
• 此外，两个点 ‘…’ 表示将目录切换到上一级（指向父目录）。
• 任意多个连续的斜杠（即，‘//’ 或 ‘///’）都被视为单个斜杠 ‘/’。
• 任何其他格式的点（例如，‘…’ 或 ‘…’）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

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

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

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，‘.’，‘/’ 或 ‘_’ 组成。
• path 是一个有效的 Unix 风格绝对路径。

2.3 解题代码

class Solution {
    public String simplifyPath(String path) {
        StringBuffer ret = new StringBuffer();
        Stack<String> stk = new Stack<>();
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < path.length(); ++i){
            if(path.charAt(i) == '/'){
                if(sb.length() != 0){
                    stk.push(sb.toString());
                }
                sb.delete(0, sb.length());
            } else{
                sb.append(path.charAt(i));
            }
        }
        if(sb.length() > 0){
            stk.push(sb.toString());
        }
        List<String> temp = new ArrayList<String>();
        while(!stk.empty()){
            if(stk.peek().equals(".")){
                stk.pop();
            } else if(stk.peek().equals("..")){
                stk.pop();
                int num = 1;
                while(!stk.empty() && num > 0){
                    if(stk.peek().equals(".")){
                        stk.pop();
                        continue;
                    } else if(stk.peek().equals("..")){
                        stk.pop();
                        num++;
                    } else{
                        stk.pop();
                        num--;
                    }
                }
            } else{
                temp.add(stk.peek());
                stk.pop();
            }
        }
        int n = temp.size();
        for(int i = n - 1; i >= 0; --i){
            ret.append("/");
            ret.append(temp.get(i));
        }
        if(n == 0){
            ret.append("/");
        }
    return ret.toString();
    }
}

2.4 解题思路

1. 先用字符串数组存储所有的字符串（以一个或多个‘/’分隔）。
2. 接着用栈来去除掉所有多余的字符串，‘.’去除栈顶一个，‘…’去除栈顶两个，如果去除的有‘…’则需要再多去除一个。其他非上述的字符串则放入字符串数组中。
3. 最后再逆序遍历该字符串数组，按照正确的格式拼接成一个字符串返回。

3、最小栈

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

提示：

• -2³¹ <= val <= 2³¹ - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 10⁴ 次

3.3 解题代码

class MinStack {
    Stack<Integer> Min = new Stack<>();
    Stack<Integer> stk = new Stack<>();
    public MinStack() {
        while(!Min.empty()){
            Min.pop();
        }
        while(!stk.empty()){
            stk.pop();
        }
    }
    
    public void push(int val) {
        stk.push(val);
        if(Min.empty()){
            Min.push(val);
        } else{
            if(val < Min.peek()){
                Min.push(val);
            } else{
                Min.push(Min.peek());
            }
        }
    }
    
    public void pop() {
        stk.pop();
        Min.pop();
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return Min.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

3.4 解题思路

1. 用一个栈正常进入入栈出栈操作。
2. 维护一个最小栈，当栈顶为空的时候正常入栈，如果栈顶非空，如果当前栈中元素大于该元素则入最小栈，否则的话则将最小栈顶元素继续入栈。

4、逆波兰表达式求值

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（“+”、“-”、“*” 或 “/”），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；
• 遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

4.3 解题代码

class Solution {

    int Alter(String s){
        int num = 0;
        if(s.charAt(0) >= '0' && s.charAt(0) <= '9'){
            for(int i = 0; i < s.length(); ++i){
                num *= 10;
                num += s.charAt(i) - '0';
            }
        } else{
            for(int i = 1; i < s.length(); ++i){
                num *= 10;
                num += s.charAt(i) - '0';
            }
            num *= -1;
        }
    return num;
    }

    int calculate(char ch, int num1, int num2){
        if(ch == '+'){
            return num2 + num1;
        } else if(ch == '-'){
            return num2 - num1;
        } else if(ch == '*'){
            return num2 * num1;
        } else if(ch == '/'){
            return num2 / num1;
        }
    return -1;
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stk = new Stack<>();
        int n = tokens.length;
        for(int i = 0; i < n; ++i){
            String str = tokens[i];
            if(!str.equals("+") && !str.equals("-") && !str.equals("*") && !str.equals("/")){
                stk.push(Alter(str));
            } else{
                int num1 = stk.peek();
                stk.pop();
                int num2 = stk.peek();
                stk.pop();
                stk.push(calculate(str.charAt(0), num1, num2));
            }
        }
    return stk.peek();
    }
}

4.4 解题思路

1. 用栈直接模拟逆波兰表达式的过程即可。

5、基本计算器

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

提示：

• 1 <= s.length <= 3 * 10⁵
• s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
• s 表示一个有效的表达式
• ‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
• ‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

5.3 解题代码

class Solution {

    public int calculate(String s) {
        int sum = 0;
        int i = 0;
        int n = s.length();
        Stack<Integer> stk = new Stack<>();
        int sign = 1;
        stk.push(1); // 一开始默认是加号
        while(i < n){
            char ch = s.charAt(i);
            if(ch == ' '){
                ++i;
            } else if(ch == '+'){
                sign = stk.peek();      
                ++i;
            } else if(ch == '-'){
                sign = (stk.peek() * -1);
                ++i;
            } else if(ch == '('){
                stk.push(sign);
                ++i;
            } else if(ch == ')'){
                stk.pop();
                ++i;
            } else{
                int num = 0;
                while(i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                    num *= 10;
                    num += s.charAt(i) - '0';
                    ++i;
                }
                sum += sign * num;
            }            
        }
        return sum;
    }
}

5.4 解题思路

1. 首先往栈顶放入数字1，表示加号。
2. 如果碰到‘+’则符号位设置为栈顶元素，如果碰到‘-’则符号位设置为栈顶元素 * -1，如果遇到左括号，则当前符号为负，则往栈顶元素放入-1，反之则为1，即当前存储的符号位。
3. 从左往后每次遇到数字则结果加上符号位 * 数字即可。