leetcode|leetcode 241. Different Ways to Add Parentheses 为运算表达式设计优先级(中等) leetcode241.DifferentWaystoAddParent

一、题目大意标签: 分治
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]

二、解题思路 【leetcode|leetcode 241. Different Ways to Add Parentheses 为运算表达式设计优先级(中等)】题目中的例子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 diffWaysToCompute(String expression) { List ans = new ArrayList<>(); for (int i = 0; i < expression.length(); i++) { char ope = expression.charAt(i); if (ope == '+' || ope == '-' || ope == '*') { List left = diffWaysToCompute(expression.substring(0, i)); List 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; } }

四、总结小记