leetcode经典算法题总结

        针对leetcode算法题常见的五大经典复杂算法进行如下总结：

 （1）分治法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问题的解，就可得到原问题的解。应用：快速排序、归并排序、二分查找、大整数乘法、矩阵乘法等。对应解题模版如下：

function divideAndConquer(problem)// 如果问题是最简单的情况if problem is trivial// 直接解决问题return solveTrivially(problem)// 将问题分解为子问题divide problem into subproblems// 创建一个数组来存储子问题的解subSolutions = []// 遍历每个子问题for each subproblem in subproblems// 递归解决每个子问题，并将解添加到数组中subSolutions.append(divideAndConquer(subproblem))// 合并子问题的解来解决原始问题return merge(subSolutions)

 （2）动态规划法

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。通常用一个表来记录所有已解的子问题的答案。应用：斐波那契数列、背包问题、最长公共子序列、最短路径问题等。对应解题模板如下：

function dynamicProgramming(problem)// 创建一个表格来存储子问题的解create table dp of dimensions appropriate for problem// 对于每个初始状态for each initial state// 设置基本情况的解dp[initial state] = baseCase(initial state)// 按照子问题的大小递增顺序进行for each subproblem in increasing order of size// 对于每个可能的决策for each possible decision// 对于每个由决策导致的状态for each state resulting from decision// 更新状态的解dp[state] = min(dp[state], dp[previous state] + cost of decision)// 返回最终状态的解return dp[final state]

 （3）贪心算法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 常见的贪心算法有：Prim算法、Kruskal算法（都是求最小生成树的）。基本思路：将问题分解为若干个小问题，逐渐求得各个子问题的局部最优解，最后合并为原来问题的解。由于总是做出在当前看来是最好的选择，可能最后得到的结果不是全局最优，是一种特殊的动态规划。应用：霍夫曼编码、最小生成树（Kruskal算法、Prim算法）、任务调度、区间调度等。对应解题模板如下：

function greedyAlgorithm(problem)// 如果问题是最简单的情况if problem is trivial// 直接解决问题return solveTrivially(problem)// 当问题未解决时while not done// 找到当前状态下的最优选择bestChoice = findBestChoice(current state)// 根据选择更新当前状态current state = makeChoice(bestChoice)// 返回当前状态return current state

 （4）回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。深度优先；回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。应用：八皇后问题、数独、子集和问题、排列组合问题等。对应解题模板如下：

function backtrack(problem, state)// 如果当前状态是目标状态if state is goal state// 返回truereturn true// 遍历每个可能的移动for each possible move from state// 如果移动是安全的if move is safe// 执行移动make move// 递归地探索新状态if backtrack(problem, new state)// 如果找到解决方案，返回truereturn true// 回溯到之前的状态backtrack(problem, previous state)// 撤销移动undo move// 如果没有找到解决方案，返回falsereturn false

 （5）分支限界法

类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。常见有队列式(FIFO)分支限界法和优先队列式分支限界法，应用：旅行商问题（TSP）、车辆路径问题（VRP）、背包问题等。对应解题模板如下：

function branchAndBound(problem)// 创建一个优先队列create a priority queue Q// 将问题的初始状态入队enqueue initial state of problem into Q// 当队列不为空时while Q is not empty// 出队一个当前状态current state = dequeue Q// 如果当前状态是目标状态if current state is goal state// 返回truereturn true// 遍历当前状态的每个子状态for each child of current state// 如果子状态比当前界限更好if child is better than current bound// 将子状态和它的界限入队enqueue child into Q with its bound// 如果没有找到解决方案，返回falsereturn false

       针对leetcode上的算法题，上述代码只是一个简单抛砖引玉的解题模版，还有一些约束条件或者边界条件还没细说，还是需要结合具体题目进行多加历练才行。