盐城营销网站建设,wordpress同步到公众号,wordpress登录安全插件,市场监督管理局职责文章目录1 题目理解2 分治法1 题目理解
输入#xff1a;字符串input#xff0c;包含数字和操作符 规则#xff1a;给input的不同位置加括号#xff0c;使得input可以得到不同的计算结果。 输出#xff1a;返回可能的计算结果 Example 1:
Input: “2-1-1” Output: [0, 2…
文章目录1 题目理解2 分治法1 题目理解
输入字符串input包含数字和操作符 规则给input的不同位置加括号使得input可以得到不同的计算结果。 输出返回可能的计算结果 Example 1:
Input: “2-1-1” Output: [0, 2] Explanation: ((2-1)-1) 0 (2-(1-1)) 2
2 分治法
文章参考力扣官网。 对于形如 x op y 的运算式而言它的结果取决于 x和y结果的组合数。而 x和y又别分可以写成 x op y 这样的运算式。 因此该问题中的子问题就是 x op y 需要先解决 操作符两侧算式。
1 分解按照操作符将式子分解为左右两部分 2 解决递归调用求得左右两边算式的值 3 合并根据运算符计算得到最终解
class Solution {public ListInteger diffWaysToCompute(String input) {return compute(input);}private ListInteger compute(String input){ListInteger result new ArrayListInteger();for(int i0;iinput.length();i){char op input.charAt(i);if(op || op- || op* || op/){ListInteger leftValueList compute(input.substring(0,i));ListInteger rightValueList compute(input.substring(i1));int value 0;for(int leftValue : leftValueList){for(int rightValue : rightValueList){if(op){value leftValuerightValue;}if(op-){value leftValue - rightValue;}if(op*){value leftValue * rightValue;}if(op/){value leftValue / rightValue;}result.add(value);}}}}if(result.isEmpty()){result.add(Integer.parseInt(input));}return result;}
}
