写点什么

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

作者:okokabcd
  • 2022 年 7 月 07 日
  • 本文字数:1250 字

    阅读完需:约 4 分钟

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 好事多磨,又要延期一周

发布于: 刚刚阅读数: 4
用户头像

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

评论

发布
暂无评论
leetcode 241. Different Ways to Add Parentheses 为运算表达式设计优先级(中等)_LeetCode_okokabcd_InfoQ写作社区