博客

不要纠结，干就完事了，熟练度很重要！！！多练习，多总结！！！

分治篇

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

解题思路

比如输入这样一个算式：

1 + 2 * 3 – 4 * 5

这个算式有几种加括号的方式？

(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)

其实就是按照运算符进行分割，给每个运算符的左右两部分加括号

核心逻辑如下：

List<Integer> diffWaysToCompute("(1 + 2 * 3) - (4 * 5)") {
    List<Integer> res = new LinkedList<>();
    /****** 分 ******/
    List<Integer> left = diffWaysToCompute("1 + 2 * 3");
    List<Integer> right = diffWaysToCompute("4 * 5");
    /****** 治 ******/
    for (int a : left)
        for (int b : right)
            res.add(a - b);

    return res;
}

代码实现

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < expression.length();i++){
            char c = expression.charAt(i);
            if(c == '+' || c == '-' || c == '*'){
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1));
                for(int a:left){
                    for(int b:right){
                        if(c == '+'){
                            res.add(a+b);
                        }else if(c == '-'){
                            res.add(a-b);
                        }else if(c == '*'){
                            res.add(a*b);
                        }
                    }
                }
            }
        }

        if(res.isEmpty()){
            res.add(Integer.parseInt(expression));
        }
        return res;
    }
}

总结

本题来源于

Leetcode

中 归属于

分治、贪心专题

类型题目。

同许多在算法道路上不断前行的人一样，不断练习，修炼自己！

如有博客中存在的疑问或者建议，可以在下方留言一起交流，感谢各位！

觉得本博客有用的客官，可以给个点赞+收藏哦！ 嘿嘿

喜欢本系列博客的可以关注下，以后除了会继续更新面试手撕代码文章外，还会出其他系列的文章！