【分治算法】运算的优先级

最典型的回溯算法就是归并排序，核心逻辑如下：

public void sort(int[] nums, int lo, int ho){
		int mid = (lo + hi) / 2;
		//对数组的两部分分别排序
		sort(nums,lo, mid);
		sort(nums, mid+1,hi);
		//合并两个排好序的子数组
		merge(nums, lo, mid, hi);
}

添加括号的所有方式

你输入一个算式，你可以给它随意加括号，请你穷举出全部所有的可能的加括号的结果。

List<Integer> diffWaysToCompute(String input);

解决办法的关键有两点：
1.不要思考整体，而是要目光聚焦局部，只看一个运算符
2.明确递归函数是什么，并且相信函数的定义
例如我们输入一个算式：

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)

发现规律了吗，我们其实就是按照运算符进行分隔，并且给每个运算符的左右加括号。

仔细分析

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

我们用-号进行分隔，把原算式分隔为两个算式

1 + 2 * 3

和

4 * 5

分治算法这一步就是将原问题进行分解了，我们现在要【治】了

1 + 2 * 3 

可以有两种加括号的方式，分别是

(1) + (2 * 3) = 7

和

(1 + 2) * (3) = 9

所以我们可以将这个数据写成

[7,9]

4*5只有一个数字，那就是

[20]

所以 (1 + 2 * 3) - (4 * 5) 有两种结果，分别是

9 - 20 = -11

和

7 - 20 = -13

那么，对于 (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;
}

diffWaysToCompute函数是计算当前输入的函数可以得到的函数值。

public List<Integer> diffWaysToCompute(String input){
		List<Integer> res = new LinkedList<>();
		for(int i = 0; i < input.length(); i++){
			char c = input.chatAt(i);
			if(c == '-' || c == '*' || c == '+'){
					List<Integer> left = diffWaysToCompute(input.substring(0,i));
					List<Integer> right = diffWaysToCompute(input.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(input));
    }
    return res;
}

扫描输入的算式input，每当遇到输入的运算符号就进行分隔，递归结果计算出来后，根据运算结果来合并结果。

当然，还有一个重点的函数

// base case
// 如果 res 为空，说明算式是一个数字，没有运算符
if (res.isEmpty()) {
    res.add(Integer.parseInt(input));
}

递归函数需要一个base case用来结束递归，代表着你分到什么时候可以开始归一。当算是中不存在运算符的时候，就可以结束了。

总结

解决上述算法题利用了分治思想，以每个运算符作为分割点，把复杂问题分解成小的子问题，递归求解子问题，然后再通过子问题的结果计算出原问题的结果。