每日一题:241. 为运算表达式设计优先级

解题思路

分治，也可以理解为记忆化的dfs,难点在于思路保持清晰
例如表达式2-1-1
遇到第一个运算符-,开始递归分为左侧表达式2，右侧表达式1-1,符号为-

左侧表达式2递归后，为纯数字，list为{2}

右侧表达式1-1递归后，遇到运算符-，开始递归分为左侧表达式1，右侧表达式1，符号为-
左侧表达式递归后为纯数字，list为{1}
右侧表达式递归后为纯数字，list为{1}
进行计算后结果为0，最终表达式1-1结果list为{0}

{2}与{0}开始计算，运算符为-
结果为2

代码

class Solution {
    public Map<String, List<Integer>> map = new HashMap<>();
    // 记录已经计算出来的字符串对应的值，避免重复计算。
    public List<Integer> diffWaysToCompute(String expression) {
        //如果表达式已经被计算过，直接返回值
        if (map.containsKey(expression)){
            return map.get(expression);
        }
        List<Integer> nums = new ArrayList<>();
        final int length = expression.length();
        for (int i = 0; i < length; i++) {
            final char c = expression.charAt(i);
            //当前位置为运算符，开始进行分割
            if (!Character.isDigit(c)){
                final List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                final List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                for (Integer l : left) {
                    for (Integer r : right) {
                        switch(c) {
                            case '+':
                                nums.add(l + r);
                                break;
                            case '-':
                                nums.add(l - r);
                                break;
                            case '*':
                                nums.add(l * r);
                                break;
                            default:
                                break;
                        }
                    }
                }
            }
        }
        if(nums.size() == 0) {
            nums.add(Integer.valueOf(expression));
        }
        // 单独一个数字的情况 (可能出现多位数)
        map.put(expression, nums);
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43