嵌套类问题的递归解题套路

嵌套类问题的递归解题套路

嵌套类问题的解题套路

大概过程:

1)定义全局变量 int where

2)递归函数f(i) : s[i…]，从i位置出发开始解析，遇到 字符串终止 或 嵌套条件终止 就返回

3)返回值是f(i)负责这一段的结果

4)f(i)在返回前更新全局变量where，让上级函数通过where知道解析到了什么位置，进而继续

执行细节:

1)如果f(i)遇到 嵌套条件开始，就调用下级递归去处理嵌套，下级会负责嵌套部分的计算结果

f(i)下级处理完成后，f(i)可以根据下级更新的全局变量where，知道该从什么位置继续解析

题目1 : 含有嵌套的表达式求值。时间复杂度O(n)

• 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/

• 思路

  • 遍历整个字符链表, 如果没有遇到终止, 也没有遇到右括号(子过程终止的标志),
    • 遇到数字, 计算数字, 继续遍历
    • 遇到运算符, 加入运算符链表中
    • 遇到左括号, 调用子过程嵌套计算, 子过程会将where更新到它的右括号的位置, 父过程接着where+1的位置继续
  • 将最后一个数字和字符加入
  • 更新where
  • 返回两个链表的计算结果

• 代码

  • 	public static int calculate(String str) {where = 0;return f(str.toCharArray(), 0);}public static int where;// s[i....]开始计算，遇到字符串终止 或者 遇到)停止// 返回 : 自己负责的这一段，计算的结果// 返回之前，更新全局变量where，为了 上游函数 知道从哪继续！public static int f(char[] s, int i) {int cur = 0;ArrayList<Integer> numbers = new ArrayList<>();ArrayList<Character> ops = new ArrayList<>();while (i < s.length && s[i] != ')') {// 当前没有遇到终止, 也没有遇到右括号if (s[i] >= '0' && s[i] <= '9') {// 遇到数字cur = cur * 10 + s[i++] - '0';// 计算数字, 继续遍历} else if (s[i] != '(') {// 没有遇到 ), 数字, (// 遇到了运算符 + - * /push(numbers, ops, cur, s[i++]);// 往堆里加cur = 0;// 数字清空成0} else {// i (.....)// 遇到了左括号！cur = f(s, i + 1);// 子过程计算嵌套i = where + 1;// 接着where + 1继续}}// endWhilepush(numbers, ops, cur, '+');// 加入最后一个数字, 默认补个加号where = i;// 更新从while里跳出时的where(右括号)return compute(numbers, ops);// 最终对+-的计算}public static void push(ArrayList<Integer> numbers, ArrayList<Character> ops, int cur, char op) {int n = numbers.size();if (n == 0 || ops.get(n - 1) == '+' || ops.get(n - 1) == '-') {// 第一个进栈 或 栈顶不是+/- 直接加numbers.add(cur);ops.add(op);} else {// 遇到 * /int topNumber = numbers.get(n - 1);// 弹出顶部的数字char topOp = ops.get(n - 1);// 弹出顶部的符号// 结合, 加进数字栈if (topOp == '*') {numbers.set(n - 1, topNumber * cur);// 原来有数字, 使用set覆盖} else {numbers.set(n - 1, topNumber / cur);}// 加进操作符栈ops.set(n - 1, op);}}public static int compute(ArrayList<Integer> numbers, ArrayList<Character> ops) {// 计算最后的加减运算int n = numbers.size();int ans = numbers.get(0);for (int i = 1; i < n; i++) {ans += ops.get(i - 1) == '+' ? numbers.get(i) : -numbers.get(i);}return ans;}
    

题目2 : 含有嵌套的字符串解码。时间复杂度O(n)

• 测试链接 : https://leetcode.cn/problems/decode-string/

• 思路 同大致过程 相同

• 代码

  • 	public static String decodeString(String str) {where = 0;return f(str.toCharArray(), 0);}public static int where;// s[i....]开始计算，遇到字符串终止 或者 遇到 ] 停止// 返回 : 自己负责的这一段字符串的结果// 返回之前，更新全局变量where，为了上游函数知道从哪继续！public static String f(char[] s, int i) {StringBuilder path = new StringBuilder();int cnt = 0;while (i < s.length && s[i] != ']') {// 没有遇到终止条件if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {// 遇到字母path.append(s[i++]);// 直接往path里面加} else if (s[i] >= '0' && s[i] <= '9') {// 遇到数字cnt = cnt * 10 + s[i++] - '0';// cnt开始累加} else {// 遇到 [ // cnt = 7 * ? path.append(get(cnt, f(s, i + 1)));i = where + 1;// 子过程告诉我从哪里继续cnt = 0;// 数字清空!!!!}}where = i;// 在where中更新计算到哪return path.toString();// 返回path}public static String get(int cnt, String str) {StringBuilder builder = new StringBuilder();for (int i = 0; i < cnt; i++) {builder.append(str);}return builder.toString();}
    

题目3 : 含有嵌套的分子式求原子数量。时间复杂度O(n)

• 测试链接 : https://leetcode.cn/problems/number-of-atoms/

• 思路

  • 思路 同大致过程 相同
  • 此处注意要记录的分为普通的字符串 和 进行递归时保存的有序表

• 代码

  • 	public static String countOfAtoms(String str) {where = 0;TreeMap<String, Integer> map = f(str.toCharArray(), 0);// 有序表用于保存字母和次数StringBuilder ans = new StringBuilder();// ans用于追加答案for (String key : map.keySet()) {ans.append(key);int cnt = map.get(key);if (cnt > 1) {// 只有cnt>1 才往后拼数字, =1 不拼ans.append(cnt);}}return ans.toString();}public static int where;// s[i....]开始计算，遇到字符串终止 或者 遇到 ) 停止// 返回 : 自己负责的这一段字符串的结果，有序表！// 返回之间，更新全局变量where，为了上游函数知道从哪继续！public static TreeMap<String, Integer> f(char[] s, int i) {// ans是总表TreeMap<String, Integer> ans = new TreeMap<>();// 之前收集到的名字，历史一部分StringBuilder name = new StringBuilder();// 之前收集到的元素名字(如: H,Fe,Mg,O)，历史一部分TreeMap<String, Integer> pre = null;// 等着被传// 历史翻几倍int cnt = 0;while (i < s.length && s[i] != ')') {// &&!!!if (s[i] >= 'A' && s[i] <= 'Z' || s[i] == '(') {// 遇到 大写 或 ( : 更新历史// 更新历史fill(ans, name, pre, cnt);// 清空历史name.setLength(0);//!!!pre = null;cnt = 0;if (s[i] >= 'A' && s[i] <= 'Z') {// 遇到的是大写字母name.append(s[i++]);// 加入name} else {// 遇到 ( : 交给递归执行(由于要++,最好不用if)pre = f(s, i + 1);// 告诉你小表是什么i = where + 1;// 接着where计算}} else if (s[i] >= 'a' && s[i] <= 'z') {// 遇到小写, 说明要把name补完整 : Fename.append(s[i++]);} else {cnt = cnt * 10 + s[i++] - '0';// 遇到数字, 计算数字}}fill(ans, name, pre, cnt);// 从where跳出来之后再加一次历史, 最后走到头的时候没有 大写字母 或 (where = i;// i填到where去return ans;// 返回表}public static void fill(TreeMap<String, Integer> ans, StringBuilder name, TreeMap<String, Integer> pre, int cnt) {if (name.length() > 0 || pre != null) {// 有历史, pre要么为null, 要么有有效值//(不一定有历史, 比如若开头是大写字母或(, 此时没有历史, 但符合进入函数的要求, 此时不需要进行处理)cnt = cnt == 0 ? 1 : cnt;// cnt表示词频if (name.length() > 0) {// nameString key = name.toString();ans.put(key, ans.getOrDefault(key, 0) + cnt);// 更新name的词频(在原来的词频上加} else {for (String key : pre.keySet()) {// 更新小表, 原子数为小表字母下标 * cnt(词频) (在原来的词频上加ans.put(key, ans.getOrDefault(key, 0) + pre.get(key) * cnt);// put不是add}}}}