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

2023-12-19 05:38:08

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

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用来结束递归,代表着你分到什么时候可以开始归一。当算是中不存在运算符的时候,就可以结束了。

总结

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

文章来源:https://blog.csdn.net/buzhbuzh/article/details/135073261
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。