算法思想 - 分治算法

提示

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

• 分治相关题目
  • 给表达式加括号

分治相关题目

给表达式加括号

[ 241. Different Ways to Add Parentheses (Medium) 在新窗口打开 ](https://leetcode.com/problems/different-ways-to-add- parentheses/description/)

    Input: "2-1-1".
    
    ((2-1)-1) = 0
    (2-(1-1)) = 2
    
    Output : [0, 2]
    

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ways = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+':
                                ways.add(l + r);
                                break;
                            case '-':
                                ways.add(l - r);
                                break;
                            case '*':
                                ways.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (ways.size() == 0) {
            ways.add(Integer.valueOf(input));
        }
        return ways;
    }