【分治算法】运算的优先级
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!