LeetCode 241. 为运算表达式设计优先级

àì夳堔傛蜴生んèń 2022-10-29 07:37 120阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[大佬题解][Link 1]

class Solution {
        
        public List<Integer> diffWaysToCompute(String input) {
        
            List<Integer> res = new LinkedList<>();//这里要注意，每一个调用递归函数都会有一个【属于】本次
            // 调用的res列表存放数据
            // 递归函数传参传进来的是上一层左半部分或者右半部分
            for(int i=0;i<input.length();i++){
          //一层（一次函数调用中）需要将传入数字符串遍历完
                char temp = input.charAt(i);
                if(temp == '+' || temp == '-' || temp == '*'){
        
                    List<Integer> left = diffWaysToCompute(input.substring(0,i));
                    List<Integer> right = diffWaysToCompute(input.substring(i+1));
                    for(int l:left){
        
                        for(int r:right){
        
                            if(temp == '-'){
        
                                res.add(l-r);//而一层中只有一个res用于存放数据
                            }else if(temp == '+'){
        
                                res.add(l+r);
                            }else if(temp == '*'){
        
                                res.add(l*r);
                            }
                        }
                    }
                }
            }
            //这种情况是只有一个数字字符传入了递归函数，那么该次调用直接返回该数值的list集合
            if(res.size() == 0){
        
                res.add(Integer.valueOf(input));
                return res;
            }
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/e13b2b34105b4195860ede3ffa501fe0.png
[Link 1]: https://leetcode-cn.com/problems/different-ways-to-add-parentheses/solution/wei-yun-suan-biao-da-shi-she-ji-you-xian-gb6e/