241. Different Ways to Add Parentheses

iven a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Example 1:

1
2
3
4
5
Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10
 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> nums = new ArrayList<>();
        List<String> operaters = new ArrayList<>();
        split(input,nums,operaters);//以后有想法就先把函数写出来再说
        return calculate(nums, operaters, 0, nums.size()-1);
    }

    private void split(String input, List<Integer> nums, List<String> operaters){
        StringBuilder sb = new StringBuilder();//不需要预先设置长度
        for (int i = 0; i < input.length(); i++) {
            char character = input.charAt(i);//charAt充当遍历器
            if (character == '+' || character == '-' || character == '*'){
                nums.add(Integer.valueOf(sb.toString()));//是错位的加法
                sb = new StringBuilder();
                operaters.add(character+"");//只是为了char 2 string,一定要是双引号
            }
            else {
                sb.append(character);//这么感觉有点蠢,之后再看看
            }
        }
        nums.add(Integer.valueOf(sb.toString()));
    }

    private List<Integer> calculate(List<Integer> nums, List<String> operaters, int start, int end){
        List<Integer> res = new ArrayList<>();//这个是要返回的结果呀
        /*
        * 写结束条件
        * */
        if (start == end){
            res.add(nums.get(start));
            return res;
        }
        /*
        * 一般处理情况
        * */
        for (int i = start; i < end; i++) {
            List<Integer> left = calculate(nums, operaters, start, i);
            List<Integer> right = calculate(nums, operaters, i+1, end);
            mergelist(left, right, res, operaters.get(i));
        }
        return res;
    }

    private void mergelist(List<Integer> left, List<Integer> right, List<Integer> res, String operator){
        for (int i = 0; i < left.size(); i++) {
            for (int j = 0; j < right.size(); j++) {
                int num = operate(left.get(i), right.get(j), operator);
                res.add(num);
            }
        }
    }

    private int operate(int i, int j, String operator){
        switch (operator){
            case "+":
                return i+j;
            case "-":
                return i-j;
            case "*":
                return i*j;
        }
        return 0;
    }
}

数字符合种类合集 - 分治的思想 - 程序较为复杂,自己还hold不住 - 对于string字符串中数据的提取很不熟练 - 对于switch基本函数的运用 - 对于stringbuilder的运用 - 递归的基本思想实践能力不行 - 程序的逻辑性分析大体倒是对了 - 最近事情多,不能静下心来思考很伤