在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希望能够按计划地有效刷题。本次刷题，我用的是 Java 语言解题，有余力的话也可能会加上 C++ 的题解。以下是算法训练营第十一天的刷题记录和思考笔记。
一、20 有效的括号 题目 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
解题思路 由于栈结构的特殊性，非常适合做对称匹配类的题目。括号匹配是使用栈解决的经典问题。在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean isValid (String s) { Deque<Character> deque = new LinkedList <>(); char ch; for (int i = 0 ; i < s.length(); i++) { ch = s.charAt(i); if (ch == '(' ) { deque.push(')' ); } else if (ch == '{' ) { deque.push('}' ); } else if (ch == '[' ) { deque.push(']' ); } else if (deque.isEmpty() || deque.peek() != ch) { return false ; } else { deque.pop(); } } return deque.isEmpty(); } }
二、1047 删除字符串中的所有相邻重复项 题目 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
1 2 3 4 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
解题思路 用栈来存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public String removeDuplicates (String s) { Deque<Character> deque = new ArrayDeque <>(); for (int i = 0 ; i < s.length(); i++) { if (deque.peek() != null && deque.peek() == s.charAt(i)) { deque.pop(); } else { deque.push(s.charAt(i)); } } String str = "" ; while (!deque.isEmpty()) { str = deque.pop() + str; } return str; } }
本题还可以拿字符串直接作为栈，用StringBuilder 来修改字符串，速度更快，也省去了栈还要转为字符串的操作。
本题还可以双指针法，直接用 fast 指针覆盖 slow 指针的值，遇到前后相同值的就跳过，即 slow 指针后退一步，下次循环就可以直接被覆盖掉了。
编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈。递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
但是在企业项目开发中，尽量不要使用递归。在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分 return 的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误。
三、150 逆波兰表达式求值 题目 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
1 2 3 输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
解题思路 其实逆波兰表达式相当于是二叉树中的后序遍历。 可以把运算符作为中间节点，按照后序遍历的规则（左右中）画出一个二叉树。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，图示即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
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 class Solution { public int evalRPN (String[] tokens) { Deque<Integer> stack = new LinkedList <Integer>(); for (String token : tokens) { if (isNumber(token)) { stack.push(Integer.parseInt(token)); } else { int num2 = stack.pop(); int num1 = stack.pop(); switch (token) { case "+" : stack.push(num1 + num2); break ; case "-" : stack.push(num1 - num2); break ; case "*" : stack.push(num1 * num2); break ; case "/" : stack.push(num1 / num2); break ; default : } } } return stack.pop(); } public boolean isNumber (String token) { return !("+" .equals(token) || "-" .equals(token) || "*" .equals(token) || "/" .equals(token)); } }
