深圳网站设计公司哪家专业,wordpress 360加速,重庆建设厂网站,唐山企业网站最典型的回溯算法就是归并排序#xff0c;核心逻辑如下#xff1a;
public void sort(int[] nums, int lo, int ho){int mid (lo hi) / 2;//对数组的两部分分别排序sort(nums,lo, mid);sort(nums, mid1,hi);//合并两个排好序的子数组merge(nums, lo, mid, hi);
}添加括号的…最典型的回溯算法就是归并排序核心逻辑如下
public void sort(int[] nums, int lo, int ho){int mid (lo hi) / 2;//对数组的两部分分别排序sort(nums,lo, mid);sort(nums, mid1,hi);//合并两个排好序的子数组merge(nums, lo, mid, hi);
}添加括号的所有方式 你输入一个算式你可以给它随意加括号请你穷举出全部所有的可能的加括号的结果。
ListInteger 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) 这个例子我们的计算逻辑其实就是这段代码
ListInteger diffWaysToCompute((1 2 * 3) - (4 * 5)) {ListInteger res new LinkedList();/****** 分 ******/ListInteger left diffWaysToCompute(1 2 * 3);ListInteger right diffWaysToCompute(4 * 5);/****** 治 ******/for (int a : left)for (int b : right)res.add(a - b);return res;
}diffWaysToCompute函数是计算当前输入的函数可以得到的函数值。
public ListInteger diffWaysToCompute(String input){ListInteger res new LinkedList();for(int i 0; i input.length(); i){char c input.chatAt(i);if(c - || c * || c ){ListInteger left diffWaysToCompute(input.substring(0,i));ListInteger right diffWaysToCompute(input.substring(i1));// 通过子问题的结果合成原问题的结果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用来结束递归代表着你分到什么时候可以开始归一。当算是中不存在运算符的时候就可以结束了。
总结
解决上述算法题利用了分治思想以每个运算符作为分割点把复杂问题分解成小的子问题递归求解子问题然后再通过子问题的结果计算出原问题的结果。
