国内大神耗时30天打造算法面试大全，99符合BATJ大厂面试需求

　　分治算法
　　一、基本概念
　　在计算机科学中，分治法是一种很重要的算法。字面上的解释是＂分而治之＂，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
　　任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需要任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
　　二、基本思想及策略
　　分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
　　分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
　　如果原问题可分割成k个子问题，10(有路可走) and (未达到目标)) // 还未回溯到头
　　5: {undefined
　　6: if(i > n) // 搜索到叶结点
　　7: {
　　8: 搜索到一个解，输出；
　　9: }
　　10: else // 处理第i个元素
　　11: {
　　12: a[i]第一个可能的值；
　　13: while(a[i]在不满足约束条件且在搜索空间内)
　　14: {undefined
　　15: a[i]下一个可能的值；
　　16: }
　　17: if(a[i]在搜索空间内)
　　18: {undefined
　　19: 标识占用的资源；
　　20: i = i+1; // 扩展下一个结点
　　21: }
　　22: else
　　23: {undefined
　　24: 清理所占的状态空间； // 回溯
　　25: i = i –1;
　　26: }
　　27: }
　　（3）递归的算法框架
　　回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
　　1: int a[n];
　　2: try(int i)
　　3: {undefined
　　4: if(i>n)
　　5: 输出结果;
　　6: else
　　7: {undefined
　　8: for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
　　9: {undefined
　　10: if(fun(j)) // 满足限界函数和约束条件
　　11: {undefined
　　12: a[i] = j;
　　13: ... // 其他操作
　　14: try(i+1);
　　15: 回溯前的清理工作（如a[i]置空值等）;
　　16: }
　　17: }
　　18: }
　　19: } 分支限界法
　　一、基本描述
　　类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
　　（1）分支搜索算法
　　所谓＂分支＂就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。
　　选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。
　　1）FIFO搜索
　　2）LIFO搜索
　　3）优先队列式搜索
　　（2）分支限界搜索算法
　　二、分支限界法的一般过程
　　由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
　　分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
　　分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
　　三、回溯法和分支限界法的一些区别
　　有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢？
　　回溯法和分支限界法的一些区别：
　　方法对解空间树的搜索方式 存储结点的常用数据结构 结点存储特性常用应用
　　回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解
　　分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解
　　小编是一个有着8年工作经验的java’开发工程师，关于java’编程，自己有做材料的整合，一个完整的java编程学习路线，学习材料和工具，能够进我的 群,私信 我收取，免费送给大家，希望你也能凭着自己的努力，成为下一个优秀的程序员
　　觉得写的还不错的就点个赞，加个关注呗！点关注，不迷路，持续更新！！！