算法-嵌套类递归解题套路

理论基础 :

嵌套类递归是指一种一个字符串形式的问题通过嵌套调用子函数从而求解出结果的一类问题, 解题方法相对来说比较的固定, 我们总结为下面的几部分
大概过程 :

1. 定义全局变量where
2. 递归函数 f ( i ) : s [ i …] 从 i 位置开始解析, 遇到 字符串终止 或者是 嵌套条件终止 就返回
3. 返回值是 f ( i ) 负责的这一段的结果
4. f ( i ) 在返回前更新全局变量where, 目的是告诉上级函数我们以及解析到了什么位置, 从而继续函数的调用
5. 执行细节 :
   5.1 : 如果 f ( i ) 遇到嵌套条件开始, 就调用下级的递归去处理嵌套, 下级会负责嵌套部分的计算结果
   5.2 : f ( i ) 下级处理后, f ( i ) 可以根据下级更新的全局变量where, 知道该从什么新的位置开始继续解析的过程
   下面是几道例题来验证我们的理论基础

1. 基本计算器

这道题是一道典型的嵌套类问题, 用递归求解的思路
我们先来看一种比较简单的情况, 就是不涉及括号的式子
举例 1 + 3 - 6 * 2 / 3 + 8 + 9 - 10
图例如下
其实就是做一个数字栈与符号栈, 我们要实现的效果是 :
当遇到 ’ + ’ 或者是 ’ - ’ 的时候就直接入符号栈, 当遇到数字的时候, 要判断符号栈栈顶的元素是不是 ’ * ’ 或者是 ’ / ’ , 如果不是的话直接入栈, 如果是的话, 就从数字栈中弹出一个元素, 然后与当前数字运算完之后的结果入数字栈, 我们把上面的过程用图描述如下

这道题用我们嵌套类递归的解题思路就是下面描述的一样
我们举下面的例子

代码实现如下

class Solution {
     public int calculate(String s) {
        //首先处理字符串s(去除空格)
        String ss = s.replace(" ","");
        return func(ss.toCharArray(),0);
    }

    //定义的全局变量where
    private int where = 0;

    //计算的主方法 func(char[] ss, int index)
    private int func(char[] exp, int i){
        //首先每一个主方法的内部都有自己的cur(值), 数字栈, 符号栈
        LinkedList<Integer> numstack = new LinkedList<>();
        LinkedList<Character> opstack = new LinkedList<>();
        int cur = 0;

        //加入不满足while循环的条件就直接停止了
        while(i < exp.length && exp[i] != ')'){
            if(exp[i] >= '0' && exp[i] <= '9'){
                //说明是数字
                cur = cur * 10 + (exp[i++] - '0');
            }else if(exp[i] != '('){
                //说明是操作符号
                push(numstack,opstack,cur,exp[i++]);
                cur = 0;
            }else{
                //说明是左括号(进入递归)
                cur = func(exp, i + 1);
                i = where + 1;
            }
        }

        //走到这一步说明该部分的所有数字已经被收集完毕, 开始进行算数运算(并更新当前的全局where)
        numstack.add(cur);
        where = i;
        return compute(numstack,opstack);
    }

    //计算的方法(我们的计算方法设计的和左神不太一样, 我们设计的是数字比符号多一个
    private int compute(LinkedList<Integer> numstack, LinkedList<Character> opstack){
        if(numstack.size() < 1) return 0;
        while(!opstack.isEmpty()){
            int left = numstack.removeFirst();
            int right = numstack.removeFirst();
            char op = opstack.removeFirst();
            numstack.addFirst(op == '+' ? left + right : left - right);
        }
        return numstack.pop();
    }

    //压入数字进入操作数栈的方法
    private void push(LinkedList<Integer> numstack, LinkedList<Character> opstack, int cur, char op){
        if(numstack.isEmpty() || opstack.isEmpty() || opstack.getLast() == '+' || opstack.getLast() == '-'){
            numstack.add(cur);
            opstack.add(op);
        }else{
            if(opstack.removeLast() == '*'){
                numstack.add(numstack.removeLast() * cur);
            }else{
                numstack.add(numstack.removeLast() / cur);
            }
        }
    }
}

2. 字符串解码

这道题的思路跟上面的那个题是一致的, 就是对嵌套的处理逻辑是不一样的, 代码实现如下

class Solution {
    public int index = 0;
    
    public String decodeString(String s) {
        char[] ch = s.toCharArray();
        return defunc(ch, 0);
    }
    
    //表示从i位置处开始解码
    private String defunc(char[] ch, int i){
        int cur = 0;
        StringBuilder sp = new StringBuilder();
        //如果不满足下面的条件说明递归已经可以结束了
        while(i < ch.length && ch[i] != ']'){
            if(ch[i] >= '0' && ch[i] <= '9'){
                //说明是数字就更新数字
                cur = cur * 10 + (ch[i++] - '0');
            }else if(ch[i] == '['){
                String res = defunc(ch, i + 1);
                for(int j = 0; j < cur; ++j){
                    sp.append(res);
                }
                cur = 0;
                i = index + 1;
            }else{
                sp.append(ch[i++]);
            }
        }
        index = i;
        return sp.toString();
    }
}

3. 求原子数量

这个题跟基本计算器返回的不一样的点就是, 我们最终返回的是一个TreeMap, 即每一个嵌套里面的原子数量的情况, 然后最后对这个红黑树进行遍历就可以得解

class Solution {
    /**
     * 原子的数量, 还是我们之前学习的那个递归的思路
     * 定义一个全局变量变量遍历的where;
     */
    private int where = 0;

    public String countOfAtoms(String formula) {
        //把字符串转化为字符数组
        char[] ch = formula.toCharArray();
        TreeMap<String, Integer> map = func(ch, 0);

        //进行拼接收尾处理
        StringBuilder sp = new StringBuilder();
        for(Map.Entry<String,Integer> elem : map.entrySet()){
            sp.append(elem.getKey());
            sp.append(elem.getValue() == 1 ? "" : elem.getValue());
        }
        return sp.toString();
    }

    //我们的主函数func返回的是一个TreeMap的原子集合
    public TreeMap<String, Integer> func(char[] ch, int i) {
        //下面是基础的所需准备
        TreeMap<String, Integer> map = new TreeMap<>();
        StringBuilder sp = new StringBuilder();
        String scur = null;
        int cur = 0;

        //当我们不满足下面的条件的时候就会自动跳出来
        while (i < ch.length && ch[i] != ')') {
            if (ch[i] >= 'A' && ch[i] <= 'Z') {
                sp.append(ch[i++]);
                while (i < ch.length && ch[i] >= 'a' && ch[i] <= 'z') {
                    sp.append(ch[i++]);
                }
                //如果中了if, 说明一定只有一个字符, 那么就直接入树
                if (i == ch.length || ch[i] >= 'A' && ch[i] <= 'Z'
                        || ch[i] == '(' || ch[i] == ')') {
                    map.put(sp.toString(), map.getOrDefault(sp.toString(), 0) + 1);
                }else{
                    scur = sp.toString();
                }
                //清空sp字符串拼接函数
                sp.delete(0, sp.length());
            } else if(i < ch.length && ch[i] >= '0' && ch[i] <= '9'){
                //如果是数字就先进行数字的拼接, 然后进行上面留下来的字符串的添加
                while(i < ch.length && ch[i] >= '0' && ch[i] <= '9'){
                    cur = cur * 10 + ch[i++] - '0';
                }
                map.put(scur, map.getOrDefault(scur, 0) + cur);
                cur = 0;
                scur = null;
            } else {
                //这里就只能碰上左括号了
                TreeMap<String,Integer> tempMap = func(ch, i + 1);
                //对来自内部的消息进行解析(更新下标的值)
                i = where + 1;
                int tempCur = 0;
                while(i < ch.length && ch[i] >= '0' && ch[i] <= '9'){
                    tempCur = tempCur * 10 + ch[i++] - '0';
                }
                //对拿到的TreeMap的值进行倍增操作
                if(tempCur != 0){
                    for(Map.Entry<String,Integer> elem : tempMap.entrySet()){
                        map.put(elem.getKey(),map.getOrDefault(elem.getKey(), 0) + tempCur * elem.getValue());
                    }
                }else{
                    for(Map.Entry<String,Integer> elem : tempMap.entrySet()){
                        map.put(elem.getKey(),map.getOrDefault(elem.getKey(), 0) + elem.getValue());
                    }
                }
            }
        }

        //退出之后记得更新全局的下标的位置
        where = i;
        return map;
    }
}