常见算法题分类总结之递归与栈(Stack)：解决表达式求值
我们先来看什么是递归
什么是递归？
从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢
！故事是什么呢？
“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！
故事是什么呢？
‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！ 故事是什么呢？……’”
递归的解题思路
递归程序的基本步骤：
(1) 初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务， 可以向函数传递参数，或者提供一个入口函数， 这个函数是非递归的，但可以为递归计算设 置种子值。
(2) 检查要处理的当前值是否已经与基线条件相匹配。如果匹配，则进行处理并返回值。
(3) 使用更小的或更简单的子问题（或多个子问题）来重新定义答案。
(4) 对子问题运行算法。
(5) 将结果合并入答案的表达式。
(6) 返回结果。
需要注意的点：
• 递归出口(终止递归的条件)
• 递归表达式(规律)
记忆化
我们将进一步研究递归可能出现的重复计算问题。 然后我们将提出一种常用的技术， 称为记忆化（memoization），可以用来避免重复计算问题
记忆化是一种优化技术，主要用于加快计算机程序的速度，方法是存储昂贵的函数调 用的结果，并在相同的输入再次出现时返回缓存的结果
简单点：就是用存储来存中间值，避免重复计算
总结
递归是一门伟大的艺术，使得程序的正确性更容易确认，而不需要牺牲性能，但这需 要程序员以一种新的眼光来研究程序设计。对新程序员 来说，命令式程序设计通常 是一个更为自然和直观的起点，这就是为什么大部分程序设计说明都集中关注命令式 语言和方法的原因。 不过，随着程序越来越复杂，递归程序设计能够让程序员以可 维护且逻辑一致的方式更好地组织代码
什么是“栈”？
关于“栈”，有一个非常贴切的例子，就是往枪里面装子弹。装子弹的时候都是从前往 后一个一个进；打枪发射子弹的时候，是后装的子弹先出，先进的子弹后出，子弹不能 从中间任意出。后进者先出，先进者后出，这就是典型的“栈”结构。
栈相对数组和链表貌似只有限制没有任何优势。其实从功能上来说，数组或链表确实可 以替代栈，但是存在即合理，每⼀种数据结构都是在特定的使⽤场景下的抽象，⽽且， 数组或链表虽然操作上的确灵活⾃由，但使⽤时就⽐较不可控，⾃然也就更容易出错。 当某个数据集合只涉及在⼀端插⼊和删除数据，并且满⾜后进先出、先进后出的特性， 这时我们就应该⾸选“栈”这种数据结构。
栈的插入删除操作 栈的操作只允许在一端插入和删除数据，仅在表尾进行插入和删除操作，这一端被称为 栈顶，另一端称为栈低，是一种“操作受限”的线性表。
push入栈：向一个栈插入新元素称为进栈（入栈或压栈）新元素放在栈顶元素上面，使 之成为新的栈顶元素； pop出栈：从一个栈删除元素称为出栈或退栈，是将栈顶元素删除掉。
⾸先取出近添加的数据的⽅法称为“后进先出”（Last In First Out）简称：LIFO
栈的应⽤场景
表达式的转换：中缀转后缀与求值
递归⽅式就是函数⾃身调⽤⾃身，当递归每次调⽤⾃身时，可以看作是⼊栈的过程，当递 归条件满⾜后，结束时递归再⼀级⼀级的返回，返回过程可以看作是出栈的过程。递归和 栈的实现过程可以看出都是符合“先进后出，后⼊先出”的原则，所以递归⽅式其实可以转 化为栈的⽅式来实现。
对于⼆叉树的遍历，先序、中序、后序遍历都可以⽤到递归⽅法实现，既然递归可以转化 为栈，那么如何把对⼆叉树的遍历也改为⽤栈的思想来实现
栈实现综合计算器
请输⼊⼀个表达式，计算式：7*2*2-5+1-5+3-3 请问计算机底层如何运算得到结果？注意不是简单的把算式列出运算，对于计算机来说他是⼀ 个字符串。
思路：
1、通过index值遍历表达式
2、如果发现是⼀个数字⼊数栈
3、如果扫描到的是符号分以下情况：
如果符号栈为空直接⼊栈
如果符号栈有操作符进⾏⽐较
如果当前的操作符的优先级⼩于或者等于栈中的操作符。需要从数栈中pop出2个 数，再从符号栈中pop出⼀个符号进⾏运算，将得到的结果⼊数栈，然后将当前 操作符⼊符号栈
如果当前的操作符的优先级⼤于栈中的操作符直接⼊符号栈。
4、当表达式扫描结束就顺序的从数栈和符号栈中pop相应的数和符号并运⾏
5、后在数栈中只有⼀个数字就是表达式的结果
/** * 有效括号 * @author: William * @time:2022-03-10 */public class Num20 {//map记录括号关系，栈放左括号public boolean isValid(String s) { Map map = new HashMap(); map.put(')', '(');map.put(']', '[');map.put('}', '{'); Stack stack = new Stack(); for(int i = 0; i < s.length(); i++){ switch(s.charAt(i)){ case '(':case '[':case '{': stack.push(s.charAt(i)); break; case ')':case ']':case '}': //栈空了或者右括号匹配不上左括号 if(stack.isEmpty() || map.get(s.charAt(i)) != stack.peek()) return false; //配对成功，弹出左括号 stack.pop(); break; } } //判断左括号有没有多 return stack.isEmpty(); } public boolean isValid1(String s) { int n = s.length(); if(n % 2 == 1) return false; Map pairs = new HashMap(){{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque stack = new LinkedList(); for(int i = 0; i < n; i++) { char ch = s.charAt(i); if(pairs.containsKey(ch)) { if(stack.isEmpty() || stack.peek() != pairs.get(ch)) { return false; } stack.pop(); }else { stack.push(ch); } } return stack.isEmpty(); }//用哈希提前返回private static final Map map = new HashMap(){{ put('{','}'); put('[',']'); put('(',')'); put('?','?'); }};public boolean isValid2(String s) { if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false; LinkedList stack = new LinkedList(){{add('?');}}; for(Character c : s.toCharArray()) { if(map.containsKey(c)) stack.add(c); else if(map.get(stack.removeLast()) != c) return false; } return stack.size() == 1; }//当括号只有对应的一种的情况boolean isValid3(String s) {int cntL = 0, cntR = 0;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') cntL++;else cntR++;if(cntL < cntR) return false;}return cntL == cntR;}//继续优化 去掉cntRboolean isValid4(String s) {int cnt = 0;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') cnt++;else cnt--;if(cnt < 0) return false;}return cnt == 0;}}/** * 表现良好的最长时间段 * @author: William * @time:2022-03-13 */public class Num1124 {//前缀和 + 单调栈public int longestWPI(int[] hours) {int n = hours.length;int[] score = new int[n];for(int i=0;i 8 ? 1 : -1;//pre[i]前i个数字的总和int[] pre = new int[n + 1];pre[0] = 0;for(int i=1;i<n+1;i++) pre[i] = pre[i-1] + score[i-1];int res = 0;Deque stack = new LinkedList();stack.addLast(0);for(int i = 1; i pre[i]) {stack.addLast(i);//栈从索引指向的元素严格单调递减}}for(int i = n; i >= 0; i--) {//从后往前遍历pre数组//说明栈顶索引到i位置的和是大于0的，是表现良好的时间段while(!stack.isEmpty() && pre[i] > pre[stack.peekLast()]) {//与栈顶索引指向元素比较，如果相减结果大于0，则一直出栈//直到不大于0为止，然后更新当前最大宽度res = Math.max(res, i - stack.pollLast());}}return res; }//查字典public int longestWPI1(int[] hours) {//cur记录前缀和，res记录最长时间段int cur = 0, res = 0;Map map = new HashMap();for(int i = 0; i 8) { cur++; } else { cur--; }if(cur > 0) {//还处于表现良好的时间段res = i + 1;}else {if(!map.containsKey(cur)) {map.put(cur, i);}if(map.containsKey(cur - 1)) {//这题的精髓res = Math.max(res, i - map.get(cur - 1));}}}return res;}//查字典数组版本-- 数组角标越界//public int longestWPI2(int[] hours) {//int n = hours.length, max = 0, score = 0;//int[] aux = new int[n + 1];//for(int i = 0; i 8 ? 1 : -1;//if(score > 0) max = i + 1;//else {//if(aux[-score] == 0) aux[-score] = i + 1;//if(aux[-score + 1] != 0) {//max = Math.max(max, i + 1 - aux[-score + 1]);//}//}//}//return max;//}}class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}TreeNode(int val, TreeNode left, TreeNode right){this.val = val;this.left = left;this.right = right;}}/** * 二叉树的后序遍历 —— 左右中 * @author: William * @time:2022-03-15 */public class Num145 {//递归解法public List postorderTraversal(TreeNode root) {List res = new ArrayList();return postorder(root, res); }public List postorder(TreeNode node, List res) { if(node != null) { postorder(node.left, res); postorder(node.right, res); res.add(node.val); } return res; }//用栈迭代 —— 中右左压入栈中public List postorderTraversal1(TreeNode root) {List res = new ArrayList();Stack stack = new Stack();while(!stack.isEmpty() || root != null) {while(root != null) {res.add(root.val);stack.push(root);root = root.right;}TreeNode cur = stack.pop();root = cur.left;}//此时集合中存的是中右左，得翻转才是后序Collections.reverse(res);return res;} }/** * 棒球比赛 * @author: William * @time:2022-03-12 */public class Num682 {public int calPoints(String[] ops) {Stack stack = new Stack();for(String op : ops) {if(op.equals("+")) {int top = stack.pop();//看题意int newtop = top + stack.peek();stack.push(top);stack.push(newtop);//前一次得分无效}else if(op.equals("C")) {stack.pop();//前一次的两倍}else if(op.equals("D")) {stack.push(2 * stack.peek());}else {//字符串转intstack.push(Integer.valueOf(op));}}//输出分数int ans = 0;for(int score : stack) ans += score;//或者//while(!stack.isEmpty()) ans += stack.pop();return ans; }}/** * 验证二叉树的前序序列化 - 根左右 * @author: William * @time:2022-03-15 */public class Num331 {public boolean isValidSerialization(String preorder) {//栈中每个元素，代表对应节点处剩余槽位的数量，栈顶元素对应下一步可用槽位数Deque stack = new LinkedList();int n = preorder.length(), i = 0;stack.push(1);while(i 0) {//看另一边是不是空节点stack.push(top);}//继续往后遍历i++;}else {//读一个数字while(i 0) {stack.push(top);}stack.push(2);}}return stack.isEmpty(); }}/** * 函数的独占时间 —— 待理解 * @author: William * @time:2022-03-14 */public class Num636 {//力扣官方public int[] exclusiveTime(int n, List logs) { Stack stack = new Stack (); int[] res = new int[n]; String[] s = logs.get(0).split(":"); stack.push(Integer.parseInt(s[0])); int i = 1, prev = Integer.parseInt(s[2]); while (i < logs.size()) { s = logs.get(i).split(":"); if (s[1].equals("start")) { if (!stack.isEmpty()) res[stack.peek()] += Integer.parseInt(s[2]) - prev; stack.push(Integer.parseInt(s[0])); prev = Integer.parseInt(s[2]); } else { res[stack.peek()] += Integer.parseInt(s[2]) - prev + 1; stack.pop(); prev = Integer.parseInt(s[2]) + 1; } i++; } return res; }//法二class Task{int id;int time;boolean isStart;public Task(String[] split) {this.id = Integer.valueOf(split[0]);isStart = split[1].equals("start");this.time = Integer.valueOf(split[2]);}}public int[] exclusiveTime2(int n, List logs) {Stack stack = new Stack();int[] ans = new int[n];for(String log : logs) {Task task = new Task(log.split(":"));if(task.isStart) {stack.push(task);}else {Task last = stack.pop();int time = task.time - last.time + 1;ans[task.id] += time;if(!stack.isEmpty()) {ans[stack.peek().id] -= time;}}}return ans;}}/** * 比较退格的字符串 * @author: William * @time:2022-03-12 */public class Num844 {//处理退格字符的函数public String remove(String s){Stack stack = new Stack();for(char ch : s.toCharArray()) {if(ch == '#') {if(!stack.isEmpty()) stack.pop();}else {stack.push(ch);}}//拼接字符串String ans = "";while(!stack.isEmpty()) ans = stack.pop() + ans;return ans;}public boolean backspaceCompare(String s, String t) {return remove(s).equals(remove(t)); }//重构字符串 —— 用栈模拟public String build(String str) {StringBuffer ret = new StringBuffer();for(int i = 0; i 0) {ret.deleteCharAt(ret.length() - 1);}}}return ret.toString();}public boolean backspaceCompare1(String s, String t) { return build(s).equals(build(t)); }//双指针 public boolean backspaceCompare2(String S, String T) { //i,j两个指针分别指向两个字符串末尾 int i = S.length() - 1, j = T.length() - 1; //skip 表示当前待删除的字符的数量 int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { while (i >= 0) { if (S.charAt(i) == '#') { skipS++; i--; } else if (skipS > 0) {//说明当前字符需要删除 skipS--; i--; } else {//skip为0，不需要删除 break; } } while (j >= 0) { if (T.charAt(j) == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } if (i >= 0 && j >= 0) { if (S.charAt(i) != T.charAt(j)) return false; } else { if (i >= 0 || j >= 0) return false; } i--; j--; } return true; }}/** * 基本计算器Ⅱ * @author: William * @time:2022-03-14 */public class Num227 {public int calculate(String s) {Stack stack = new Stack(); char pre = '+'; int num = 0; int n = s.length(); for (int i = 0; i < n; i++) { //判断是不是数字 if (Character.isDigit(s.charAt(i))) { //经典字符串变数字算法 num = num * 10 + s.charAt(i) - '0'; }//当不是数字并且不是空格时或者走到最后一位了 if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) { switch (pre) { case '+': stack.push(num); break; case '-': stack.push(-num); break; case '*': stack.push(stack.pop() * num); break; default: stack.push(stack.pop() / num); } //更新符号和数字 pre = s.charAt(i); num = 0; } } int ans = 0; while (!stack.isEmpty()) { ans += stack.pop(); } return ans;}public int calculate1(String s) {//加一个结束符 会在最后进到else里 s += '#'; Stack stack = new Stack();int num = 0, lastOp = '+';for(int i = 0; i = '0' && s.charAt(i) = 1) sb.append(c); if(c == '(') level++;}return sb.toString(); }public String removeOuterParentheses1(String s) {String str = "";int opened = 0;for(char c : s.toCharArray()) {if(c == '(' && opened++ > 0) {str += c;}if(c == ')' && opened-- > 1) {str += c;}}return str;}//public String removeOuterParentheses2(String s) {int cnt = 0, start = 0;String ans = "";for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') cnt++;else cnt--;if(cnt == 0) {//起始位置和结束位置ans += s.substring(start + 1, i);start = i + 1;//更换起始位置}}return ans;}}/** * 移除无效括号 * @author: William * @time:2022-03-13 */public class Num1249 {public String minRemoveToMakeValid(String s) {//栈存储左括号的下标 数组记录无效括号的索引Stack stack = new Stack();//true：代表无效括号(因为boolean数组默认是false)boolean[] nums = new boolean[s.length()];StringBuffer sb = new StringBuffer();//遍历字符串：为(就入栈，视为无效括号并记录在数组中for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') {stack.push(i);nums[i] = true;}//如果为)，就要判断栈是否为空，为空则视为无效括号并记录在数组中if(s.charAt(i) == ')') {if(stack.isEmpty()) {nums[i] = true;}else {//栈不为空就把(出栈 并把这个(的标记改为有效括号int idx = stack.pop();nums[idx] = false;}}}//最后根据无效括号数组，删除对应位置字符for(int i = 0; i < s.length(); i++) {if(!nums[i]) {sb.append(s.charAt(i));}}return sb.toString();}//错了。。。public String minRemoveToMakeValid3(String s) {int[] needRemove = new int[s.length()];Stack stack = new Stack();for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') {//入栈的是i下标stack.push(i);}else if(s.charAt(i) == ')'){if(stack.isEmpty()) {//标记应该删掉的值needRemove[i] = 1;}else {stack.pop();}}}//左括号多的情况while(!stack.isEmpty()) {needRemove[stack.peek()] = 1;stack.pop();}String ans = "";for(int i = 0; i < s.length(); i++) {if(i != needRemove[i]) ans += s.charAt(i);}return ans;}//栈和 StringBuilderpublic String minRemoveToMakeValid1(String s) {//保存需要删除字符的索引Set needRemove = new HashSet();Stack stack = new Stack();for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') stack.push(i);if(s.charAt(i) == ')') {if(stack.isEmpty()){ needRemove.add(i); }else{ stack.pop(); }}}//根据删除字符的索引创建一个新字符串while(!stack.isEmpty()) needRemove.add(stack.pop());StringBuilder sb = new StringBuilder();for(int i = 0; i < s.length(); i++) {if(!needRemove.contains(i)) {sb.append(s.charAt(i));}}return sb.toString();}//改进的使用 StringBuilder 的两步法思路public String minRemoveToMakeValid2(String s) {//移除所有无效括号StringBuilder sb = new StringBuilder();int openSeen = 0;int balance = 0;for(int i = 0; i < s.length(); i++) {char c = s.charAt(i);if(c == '(') {openSeen++;balance++;}if(c == ')') {if(balance == 0) continue;balance--;}sb.append(c);}//移除所有左括号StringBuilder res = new StringBuilder();int openToKeep = openSeen - balance;for(int i = 0; i < sb.length(); i++) {char c = sb.charAt(i);if(c == '(') {openToKeep--;if(openToKeep push j->popint i = 0, j = 0; Stack s = new Stack(); while(j = pushed.length) break; //正常情况直接压入 s.push(pushed[i]); i++; } //没有入栈数据的时候 while(s.peek() != popped[j]) return false; s.pop(); j++; } return true; } //力扣官方 —— 贪心算法 public boolean validateStackSequences1(int[] pushed, int[] popped) { int N = pushed.length; Stack stack = new Stack(); int j = 0; for(int x : pushed) { stack.push(x); while(!stack.isEmpty() && j < N && stack.peek() == popped[j]) { stack.pop(); j++; } } //检查是不是所有值都出栈了 return j == N; } //优化后的贪心栈 public boolean validateStackSequences2(int[] pushed, int[] popped) { Stack stack = new Stack(); int i = 0; for(int cur : pushed) { stack.push(cur); while(!stack.isEmpty() && stack.peek() == popped[i]) { stack.pop(); i++; } } return stack.isEmpty(); }}