关于leetcode:leetcode-241-Different-Ways-to-Add-Parentheses-为运算表达式设计优先级中等

一、题目粗心

标签: 分治

https://leetcode.cn/problems/different-ways-to-add-parentheses

给你一个由数字和运算符组成的字符串 expression，按不同优先级组合数字和运算符，计算并返回所有可能组合的后果。你能够 按任意程序 返回答案。

生成的测试用例满足其对应输入值合乎 32 位整数范畴，不同后果的数量不超过 104。

示例 1：

输出：expression = “2-1-1”
输入：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2

示例 2：

输出：expression = “23-45″
输入：[-34,-14,-10,-10,10]
解释：
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10

提醒：

• 1 <= expression.length <= 20
• expression 由数字和算符 ‘+’、’-‘ 和 ‘*’ 组成。
• 输出表达式中的所有整数值在范畴 [0, 99] 

二、解题思路

题目中的例子 1，input 是 “2-1-1” 时，就有两种状况了，(2-1)-1 和 2-(1-1)，因为括号的不同，失去的后果也不同，但如果咱们把括号里的货色当作一个黑箱的话，那么其就变为 ()-1 和 2-()，其最终的后果跟括号内可能失去的值是非亲非故的，那么再 general 一点，实际上就能够变成 () ? () 这种模式，两个括号内别离是各自的表达式，最终会别离计算失去两个整型数组，两头的问号示意运算符，能够是加，减，或乘。那么问题就变成了从两个数组中任意选两个数字进行运算，霎时变成咱们会做的题目了有木有？而这种左右两个括号代表的黑盒子就交给递归去计算，像这种分成左右两坨的 pattern 就是赫赫有名的分治法 Divide and Conquer 了，是必须要把握的一个神器。

三、解题办法

3.1 Java 实现

public class Solution {public List<Integer> diffWaysToCompute(String expression) {List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {char ope = expression.charAt(i);
            if (ope == '+' || ope == '-' || ope == '*') {List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                for (int l : left) {for (int r : right) {switch (ope) {
                            case '+':
                                ans.add(l + r);
                                break;
                            case '-':
                                ans.add(l - r);
                                break;
                            case '*':
                                ans.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (ans.isEmpty()) {ans.add(Integer.valueOf(expression));
        }
        return ans;
    }
}

四、总结小记

• 2022/7/7 一帆风顺，又要延期一周