【LeetCode】栈、队列问题：栈常见题型

向右看齐 2022-10-29 09:11 148阅读 0赞

### 栈 ###

#### [20. 有效的括号][20.] ####

难度简单2135收藏分享切换为英文接收动态反馈

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

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

**示例 1：**

输入：s = "()"
    输出：true

**示例 2：**

输入：s = "()[]{}"
    输出：true

**题解**

class Solution { 
        public boolean isValid(String s) { 
            LinkedList<Character>  stack = new LinkedList<>();
            for(int i = 0  ; i < s.length() ; i ++){ 
                char c = s.charAt(i);
                if(c == '(' || c == '[' || c == '{'){ 
                    stack.push(c);
                }else { 
                    if(stack.size() == 0){ 
                        return false;
                    }
    
                    Character top = stack.pop();
                    if((c == ')' && top != '(') 
                            || (c == ']' && top != '[') 
                            || (c == '}' && top != '{')){ 
                        return false;
                    }
                }
            }
            
            return stack.size() == 0;
        }
    }

#### [150. 逆波兰表达式求值][150.] ####

难度中等236收藏分享切换为英文接收动态反馈

根据[ 逆波兰表示法][Link 1]，求表达式的值。

有效的运算符包括 `+`, `-`, `*`, `/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

**说明：**

*  整数除法只保留整数部分。
 *  给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

**示例 1：**

输入: ["2", "1", "+", "3", "*"]
    输出: 9
    解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

**示例 2：**

输入: ["4", "13", "5", "/", "+"]
    输出: 6
    解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

**题解**

class Solution { 
        public int evalRPN(String[] tokens) { 
            LinkedList<Integer> stack = new LinkedList<>();
        
            for(int i = 0 ; i < tokens.length ; i ++){ 
                char tokenFirst = tokens[i].charAt(0);
                if(tokens[i].length() == 1 && (tokenFirst > '9' || tokenFirst < '0')){ 
                    int a = stack.pop();
                    int b = stack.pop() ;
    
                    switch (tokenFirst){ 
                        case '+':
                            stack.push(b + a);
                            break;
                        case '-':
                            stack.push(b - a);
                            break;
                        case '*':
                            stack.push(b * a);
                            break;
                        case '/':
                            stack.push(b / a);
                            break;
                    }
                }else { 
                    stack.push(Integer.valueOf(tokens[i]));
                }
            }
    
            return stack.pop();
        }
    }

#### [71. 简化路径][71.] ####

难度中等240收藏分享切换为英文接收动态反馈

以 Unix 风格给出一个文件的**绝对路径**，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（`.`）表示当前目录本身；此外，两个点 （`..`） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：[Linux / Unix中的绝对路径 vs 相对路径][Linux _ Unix_ vs]

请注意，返回的规范路径必须始终以斜杠 `/` 开头，并且两个目录名之间必须只有一个斜杠 `/`。最后一个目录名（如果存在）**不能**以 `/` 结尾。此外，规范路径必须是表示绝对路径的**最短**字符串。

**示例 1：**

输入："/home/"
    输出："/home"
    解释：注意，最后一个目录名后面没有斜杠。

**示例 2：**

输入："/../"
    输出："/"
    解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

**题解**

class Solution { 
        public String simplifyPath(String path) { 
            LinkedList<String> stack = new LinkedList();
            String[] dirs = path.split("//*");
    
            for(int i = 1 ; i < dirs.length ; i ++){ 
                if(dirs[i].charAt(0) != '.' || dirs[i].length() > 2){ 
                    stack.push(dirs[i]);
                }else if(dirs[i].length() == 2 && stack.size() != 0){ 
                    stack.pop();
                }
            }
    
            String res = "";
            for(String s : stack){ 
                res = "/" + s + res;
            }
    
            return res.length() == 0 ? "/" : res ;
        }
    }

[20.]: https://leetcode-cn.com/problems/valid-parentheses/
[150.]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
[Link 1]: https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437
[71.]: https://leetcode-cn.com/problems/simplify-path/
[Linux _ Unix_ vs]: https://blog.csdn.net/u011327334/article/details/50355600