首页  思维导图  详情

算法设计

2020-09-22 21:40:59   0  举报





AI智能生成

清华大学算法设计课程

算法设计

算法

工作总结

软件开发

作者其他创作

大纲/内容

分治 divide and conquer

概念

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

三个基本步骤

分

治

合（关键）

常见用法

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

效果

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] 不是已经算好了只要取值的么

背包问题

这里 M[i,w] 中的 i 代表只考虑序号 <= i 的物品，w 代表此时的容量。

const items = [ { w: 1, v: 3 }, { w: 2, v: 7 }, { w: 3, v: 12 }, ]; const W = 5; //背包的最大容量 console.log(knapsack(items, W));

二维数组的构成

代码中生成的二维数组

课后练习

走台阶

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）代表有多少个台阶，元素值代表此台阶级数（第几个元素）下有多少种走法 //将结果缓存在对象中会比数组好理解，以后用对象来存结果 let M = [0, 1, 1]; for (let i = 3; i < n; i++) { M[i] = M[i - 2] + M[i - 3]; } return M[n - 1]; } console.log(steps(10));

多项式最大值

Using dynamic programming to solve the following integer linear programming, the objective value is _____

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 }

其他题目

注意在很多涉及到递归的动态规划算法里其核心函数需要接收一些 在递归过程中不断变化的参数（一般是数组）（这倒也呼应了“动态规划”这个术语）， 如下面两题的 result 参数。 这时候调用递归函数时不能改变原来的参数值（状态）。 当参数为引用类型时需要好好注意！！！ 对于数组类型的参数，用 concat , slice 等不改变原数组的方法返回新数组当参数， 不要用 push 或者 splice 这些会改变原数组的变异方法。 对于对象类型的参数，也不能改变原对象，要保持原对象不变，生成新的对象当参数。

全排列

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

// 全排列 2019.12.18 闭卷手写成功开心^3^ // [1,2,3]=> // [1,2,3] [1,3,2] // [2,1,3] [2,3,1] // [3,1,2] [3,2,1] function allSequence(arr) { // 思路是 result 参数是用来携带排列结果的数组 // 循环 source 中的项目，从 source 参数中选一项，push 到递归函数的 result 参数里， // 同时递归函数的 source 参数要减少这一项 const arrangeOneFromSource = function(result, source) { if (source.length === 0) { // 递归出口一个排列完成了 // 处理排列结果这里就打印好了 console.log(result); return result; } // 这下面算是动态规划的基本思路 for (let i = 0; i < source.length; i++) { const ele = source[i]; // 注意递归调用时不能改变原 result 与 source 入参， // 不然一次排列完成后，原 result 参数已经是第一种排列的结果，source 参数也成了空数组， // source.length===0，这个循环体也不会再执行了 // 要生成新的数组当递归函数的入参 // 用 concat 与 slice 来生成新的数组 // 不要用 push 或 splice 来改变原数组 // 这个函数算尾递归 arrangeOneFromSource(     result.concat([ele]),     source.slice(0, i).concat(source.slice(i + 1)) ); } }; // 初始调用 arrangeOneFromSource([], arr); } allSequence([1, 2]);

八皇后

//  八皇后 12.20日闭卷手写 //  8*8棋盘的里面的位置描述： // 2020/01/24 // 其实就用一个一维的数组就可以表示，下标表示行，下标对应的值表示这行的棋子放哪列 eightQueen(); function eightQueen() { //这里的 count 一定要定义在调用 processLine 方法的前面 let count = 0; processLine(0, []); function processLine(n, result) { if (n === 8) { //出口，处理结果 console.log(result); console.log(++count); return result; } // 下面算是动态规划的基本思路 // 尝试每一列的位置 for (let j = 0; j < 8; j++) { let curPos = j; // 判断是否和之前的项目不冲突 if (!isConflict(result, curPos)) { // 不冲突就进入下一行 // 递归调用函数时 result 参数合并上此位置 // 这里不能用 push 改原 result 参数数组， // 不然在同一行遍历下一个位置的时候，result 参数已经被塞过上一轮的数值了   processLine(n + 1, result.concat([curPos])); } } } function isConflict(arr, item) { let arrL = arr.length; for (let i = 0; i < arrL; i++) { const ele = arr[i]; if (isConflictWithItem([i, ele], [arrL, item])) { return true; } } return false; } //[r1,c1],[r1,c1] function isConflictWithItem([r1, c1], [r2, c2]) { if (r1 === r2 || c1 === c2) return true; let rowDis = r1 - r2, colDis = c1 - c2; if (rowDis === colDis || rowDis === -colDis) return true; return false; } }

二维数组环形遍历

// 二维数组环形遍历 const arr = [ [1, 2, 3, 31], [4, 5, 6, 61], [7, 8, 9, 91], [10, 11, 12, 13] ]; const arr1 = [ [1, 2, 3, 31], [4, 5, 6, 61], [7, 8, 9, 91] ]; const arr2 = [ [1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12] ]; circleTraverse(arr2);

最长递增子序列

最长递增子序列意思是在一组数字中，找出最长一串递增的数字，比如 0, 3, 4, 17, 2, 8, 6, 10 对于以上这串数字来说，最长递增子序列就是 0, 3, 4, 8, 10，可以通过以下表格更清晰的理解

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

这个问题的动态思路解法很简单，直接上代码 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++) {   if (n[i] > n[j]) {     array[i] = Math.max(array[i], 1 + array[j])   } } } let res = 1 for (let i = 0; i < array.length; i++) { res = Math.max(res, array[i]) } return res

参考

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

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

给出一个实际金额，比如40 以及一个优惠券面额列表比如[30, 50, 100],每种优惠券数量不限 要求返回能组合成实际金额的最大值， 比如：实际金额40 -> 返回30； 80 -> 80=30+50； 110 -> 110=30+30+50

测试

console.log('10:',maxMoney(10)); console.log('30:',maxMoney(30)); console.log("40:", maxMoney(40)); console.log("80:", maxMoney(80)); console.log("180:", maxMoney(180));

代码

图

连通性与最短路径

广度优先搜索

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

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

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

换硬币问题

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

美国邮政系统

区间安排 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 在循环体中找到与结果集兼容的项目，添加到结果集中，动态修改了结果集 之后的项目在运行循环体时就需要与新的结果集兼容了

不知道项目数量的用 while 循环, 知道的用 for 循环

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

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

[Fewest conflicts] For each job, count the number of conflicting jobs cj. Schedule in ascending order of conflicts cj.

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

最早开始时间算法

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

最小延迟

[Shortest processing time first] Consider jobs in ascending order of 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 算法

子主题

最小扩展树

应用

network design

telephone, electrical, hydraulic, TV cable, computer, road

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

traveling salesperson problem, Steiner tree

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

Start with some root node s and greedily grow a tree T from s outward. At each step, add the cheapest edge e to T that has exactly one endpoint in T.

聚类

k-clustering

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

Single-link k-clustering algorithm

Form a graph on the vertex set U, corresponding to n clusters.(n 个点就初始化为 n 个聚类) Find the closest pair of objects such that each object is in a different cluster, and add an edge between them.（找到并连接最近的聚类，聚类数量-1） Repeat n-k times until there are exactly k clusters.

找到最近的聚类

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

回溯

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

基本思想

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

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

典型问题

八皇后

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

代码