算法设计

算法设计

分治divide and conquer

概念

基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，合并得到原问题的解。

三个基本步骤

分

治

合（关键）

常见用法

Break up problem of size n into two equal parts of size 1⁄2 n.Solve two parts recursively.Combine two solutions into overall solution in linear time.

效果

Brute force: n2.Divide-and-conquer: n log n.（以2为底）

归并排序

n Divide array into two halves.n Recursively sort each half.n Merge two halves to make sorted whole.

merge efficiently

双指针法

计算逆序数

最近点对

动态规划

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。还是把问题划分为子问题，但是子问题相互关联（与分治法的不同之处）。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

基本步骤/一般套路：1.列出动态规划基本方程（注意有些并没有类似“加权区间安排”问题那样的较简单清晰的基本方程，有些问题可能并不好归纳出方程，直接通过文字与代码来表达更简单）2.不少问题需要用到递归  (1)要缓存子问题的结果  (2)从底向上比从上往底效率高  可以从底向上计算M[i]/M[i][j] 的值  从底向上其实就是用的尾递归，尾递归可以大大缩减使用的栈空间

加权区间安排

Greedy algorithm works if all weights are 1.

动态规划基本方程

p(j) = largest index i < j such that job i is compatible with j.

Finding a Solution目前理解应该是找到使结果最优的元素搭配

这里 Find-Solution 是一个函数名字。实现中也用到了递归。

从底向上

分段最小二乘

这里对 n3 的来源不懂， eij 和M[i-1] 不是已经算好了只要取值的么

背包问题

这里 font color=\"#16884a\

二维数组的构成

代码中生成的二维数组

课后练习

走台阶

There is a stairs with a height of 10 steps. You can climb stairs only by two or three steps. So you can go by _____ different kinds of ways.

function steps(n) { //第几个元素（元素下标+1）代表有多少个台阶，元素值代表此台阶级数（第几个元素）下有多少种走法font color=\"#c41230\

多项式最大值

integerLinear();function integerLinear() { let Max=10;//此题 x1 x2 x3 都为0时的结果//循环的初始条件用到了动态规划 for (let x1 = 0; x1 <= 4; x1++) { for (let x2 = 4 - x1; x2 >= 0; x2--) { for (let x3 = 4 - x1 - x2; x3 >= 0; x3--) { let value = 5 * x1 * x1 + 3 * x2 * x2 + x3 * x3 - 10 * x1 - 3 * x2 + 2 * x3 + 10; if(value>Max){ Max=value } } } } console.log(Max) return Max}

其他题目

b style=\

全排列

下面的方式是我 2019.12.18 闭卷手写的，用了尾递归的方案注意递归调用时不能改变原 result 与 source

八皇后

二维数组环形遍历

最长递增子序列

通过以上表格可以很清晰的发现一个规律，找出刚好比当前数字小的数，并且在小的数组成的长度基础上加一。

这个问题的动态思路解法很简单，直接上代码function lis(n) { if (n.length === 0) return 0 // 创建一个和参数相同大小的数组，并填充值为 1 let array = new Array(n.length).fill(1) // 从索引 1 开始遍历，因为数组已经所有都填充为 1 了 for (let i = 1; i < n.length; i++) { // 从索引 0 遍历到 i // 判断索引 i 上的值是否大于之前的值 for (let j = 0; j < i; j++) {  font color=\"#16884a\

参考

file:///Users/lucy/books/FE/前端面试之道/32-常考算法题解析.htm

数钱猿辅导网上搜集面试题

测试

代码

学堂在线 | 算法设计与分析

图

连通性与最短路径

广度优先搜索

可以用 queue 实现，在 while 循环中动态 push 与 shift，直到 queue 清空其他实现方式待会查

贪婪算法都要先将项目根据一个希望对其贪婪的指标排序

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解。贪心算法在某些情况下可能都得不到结果。

换硬币问题

类似换硬币的问题中贪婪算法不一定是最优解。可能使用贪婪算法会得不到解，如下目标：140面值：100 70

美国邮政系统

一般套路：1.按照某个指标将原始数据排序2.用 while 循环2.1在循环体中得到部分最优解2.2改变循环条件2.3循环体中也要设置终止条件

区间安排interval scheduling

 [Earliest start time] Consider jobs in ascending order of start time sj.

 [Earliest finish time] Consider jobs in ascending order of finish time fj

唯一可能是最优的算法

一般套路：1.按照某个指标将原始数据排序2.用 for 循环2.1 在循环体中找到与结果集兼容的项目，添加到结果集中，动态修改了结果集之后的项目在运行循环体时就需要与新的结果集兼容了

区间安排问题中贪婪算法是最优解

[Shortest interval] Consider jobs in ascending order of interval length fj - sj.

区间划分（如给若干讲座分配最少教室）interval partioning

最早开始时间算法

区间划分中贪婪算法是最优解

最小延迟

 [Shortest processing time first] Consider jobs in ascending orderof processing time tj.

 [Earliest deadline first] Consider jobs in ascending order of deadline dj.

[Smallest slack] Consider jobs in ascending order of slack dj - tj.

优化缓存

剔除未来最远的元素(Farthest-in-future)

是最优算法，证明其最优内容比较多，以后有需要再看

最短路径

dijkstra 算法

子主题

目前看来js中实现起来应该就是广度优先搜索的方式。在当前节点将要给队列中 push 下一层的节点的时候，先判断当前处理的子元素是否被处理过（可以根据是否有属性 d 来判断）。被处理过的就更新最短路径属性，没有被处理过的就增加最短路径属性 d ，并且推入到 queue 中。但是这里不能将节点shift掉，要根据指针是否大于“节点个数-1”来判断终止条件，或者直接判断 queue[i]是否为 undefined 也能达到效果。我这里的实现和 Dijkstra 不太一样，Dijkstra 不会去更新已经探索过的点。这样可能会有错误，如1->2 101->3 13->2 1

最小扩展树

应用

network design

approximation algorithms for NP-hard problems（这里不懂，以后需要了再了解）

Cluster analysis.（同上，以后需要了再了解）

算法

Kruskal's algorithm（目前感觉这个算法思路与实现更简单）

Start with T = []. Consider edges in ascending order of cost. Insert edge e in T unless doing so would create a cycle.

Prim's algorithm

聚类

k-clustering

Divide objects into k non-empty groups. Find a k-clustering of maximum spacing

Single-link k-clustering algorithm

找到最近的聚类

This procedure is precisely Kruskal's algorithm (except we stop when there are k connected components)

回溯

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

基本思想

从一条路往前走，能进则进，不能进则退回来，换一条路再试。

回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。

典型问题

回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。