WdBly Blog

懂事、有趣、保持理智

WdBly Blog

懂事、有趣、保持理智

周维 | Jim

603927378@qq.com

前端常用算法分享

编程中常用的算法分享 包括常用排序算法 dp算法 贪心算法等

image.png

动态规划问题

动态规划 (英语:Dynamic programming,简称DP)是一种把原问题分解为相对简单的子问题的方式求解复杂问题的方法.

1.两个重要特性:最优化原理与无后效性

最优化原理:一个问题的最优解只取决于其子问题的最优解,而非最优解对问题的求解没有影响

无后效性原则:一个问题被划分成各个阶段之后,阶段K中的状态只能由阶段K+1中的状态得来,与其它状态没有关系

对于需要使用动态规划来解决的问题,必须满足三个条件:可以划分阶段,满足最优化原理,满足无后效性。误用动态规划会得到错误的结果。

数塔问题:从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值的和最大。

image.png

为什么要使用动态规划,假设数塔的层数是n层,如果我们使用枚举的方法来解决,所有可能为:2(n-1),考虑数塔问题时可以自顶向下的分析,自底向上的计算

(1)分析该问题是否能使用dp解决?

从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。同理,每一步的抉择都会由它的上一步决定满足无后效性原则。

(2)处理步骤,在分割的子问题中,每一个子问题的决策都依赖于上一个子问题的结果,在数塔的倒数第二层子问题则可以直接做出决策。

做出决策后的第四层:

image.png

这时第三层的子问题也有了答案,一直到整个数塔决策完毕

image.png

这个时候整个结果也就出来了,我们可以得知 最大的和为 59 路径也可计算出来,下面是js实现的代码

const arr = [ [9], [12,15], [10,6,8], [2,18,9,5], [19,7,10,4,16] ]; //为了方便数据操作 我们新建一个数塔用于存储决策后的新数塔 let dp = []; //将原始数据的最后一行拷贝 dp[arr.length - 1] = arr[arr.length - 1]; for(let i = arr.length - 2; i >= 0; i--){ dp[i] = []; for(let j = 0, len2 = arr[i].length; j < len2; j++){ //计算每个子问题时 将自身的值和上一个子问题的给的值相加 比较出最优的值 并赋值 let m1 = arr[i][j] + dp[i+1][j]; let m2 = arr[i][j] + dp[i+1][j+1]; dp[i][j] = m1 > m2 ? m1 : m2; }; }; console.log(dp); //求出最优解的路径 let j = 0,value,result = [arr[0][0]]; for (let i = 1, len = dp.length; i < len; ++i){ //用决策后的数据减去原始数据(同一位置)的值 必然存在于该数据的上一阶段 value = dp[i - 1][j] - arr[i - 1][j]; //因为是二叉树 这里的value必然会等于 dp[i][j] 或者 dp[i][j+1]中的一个 if (value === dp[i][j]){ result.push(arr[i][j]); }else { result.push(arr[i][++j]); } } console.log(result);

从代码中可以看出来,运用dp解决此类问题,其算法的复杂度是呈等差数列上升的,也就是说一个层数为40层的数塔计算时间几乎可以忽略不记(10毫秒以内)
经过实际的测试统计,一个层数为4000层的数塔计算时间 大约在 500毫秒以内,而如果要通过枚举则最多需要 23999 次,js支持的最大整数为21023 ,而40000层的数塔浏览器直接崩溃了?

最长不下降序列问题

不下降序列:设有一个正整数序列a[n]: a1,a2,…,an ,对于下标1<2<…<h,若有a[1]<a[2]<…a[h], 则称序列a[n]含有一个长度为h的不下降子序列。

求出随机给定的序列中的最长不下降序列
如:[5,8,2,10,1,15] 中 [2,10,15]为一个不下降序列

而 [5,8,10,15] 为一个 最长不下降序列

思考:是否能通过dp算法解决,如何分析,拆解子问题?

分析:序列中任意起点的最优(最长不下降)取决于离该起点的最近的比起点值大的节点的最优,从而可以分解为许多个子问题。
同样可以使用自左向右的分析,自右向左的计算。

假设给定一序列
image.png

序列长度表示该序列元素的所能连接的最长不下降子序列的长度,因为本身长度为1,所以初始值都为1.

从右往左计算:55>18 所以序列长度不变任为1 ,22<55 则22的序列长度应该 先找到 在22右边比22大且序列长度最大(k)的元素(可能不止一个) 然后将22链接到该元素上形成了一个长度为 k+1的序列。

同理根据这一规则可以得到每个节点的 k,最终结果如上图所示,最长不下降序列长度为 5 ,如果需要求出这个序列的话 则可以这么操作:

image.png

js代码实现(部分)

const list = [12,5,14,16,8,7,22,55,23],listLen = []; listLen[list.length - 1] = 1; for(let i = list.length - 2;i>=0;i--){ listLen[i] = 1; for(let j = i+1;j<=list.length-1;j++){ if(list[i]<list[j]){ if(listLen[i] <= listLen[j]){ listLen[i] = listLen[j]+1; } } } } console.log(listLen); //(9) [5, 5, 4, 3, 3, 3, 2, 1, 1]

贪心算法

所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

1:贪心算法和dp的比较
贪心算法:
作出的每步贪心决策都无法改变(所以导致应用贪心算法得到的不一定是最优解)

动态规划算法:
以求出的局部最优解来推导全局最优解

eg1:
要从人民币中取出16元,怎么取能取最少张?
贪心算法:20->10->5->1; 第一次拿20不符合 第二次拿10元成功。
js代码实现

//贪心算法 function greedy(money,total) { //先将金额数组排序 -> 降序 money = money.sort((a, b) => b - a); //定义最终结果 和余数 let res = 0,remainder; for(let i = 0, len = money.length; i < len; i++){ remainder = total%money[i]; //如果余数为零 可以结束循环 if(remainder === 0){ res += total/money[i]; break; }else if(remainder < total){ //如果余数不为零 res增加 total相应减少 res += (total - total%money[i])/money[i]; total = total%money[i]; } } console.log(res); //3 } greedy([1,2,5,10,20,50,100],16);

乍一看好像没什么问题,最少需要取三次,贪心算法得到了正确的结果,但是前面我们说过,贪心算法不是已整体为最优的算法,所以我们换一下题目:

要从已知币额为 1元 3元 4元的纸币中取出 6元的最少纸币数?
用贪心算法求解:

//贪心算法 function greedy(money,total) { ... console.log(res); //3 [4,1,1] } greedy([1,3,4],6);

从结果我们可以得知,使用贪心算法得到的结果并不是一个整体最优的结果(最优是两个三元的组合),这是由于贪心抉择不可改变造成的。同理在最开始我们讲的数塔问题中,如果使用贪心算法会得到什么结果呢?
9-15-8-9-10 -> 51 并不是我们的最优结果。

那么这类问题的求解需要使用dp算法来处理:

实现思路:(1)拆分子问题,判断是否满足最优化后无后效性。
(2)实现单个子问题最优,推导出整个问题最优。

思考? 如何拆分,实现

取钱问题js代码实现:

//动态规划 function MakeMoney(money,total){ let coinMoney = [0]; //i-->钱币面值,money[i]表示找零的最小硬币数 for (let i = 1; i <= total; i++){ //设定一个最多取多少张的值 后面如果有更优则直接替换 let minMoney = i; for (let j = 0; j < money.length; j++){ if (i >= money[j]) { let tmp = coinMoney[i - money[j]] + 1; if (tmp < minMoney){ //替换 minMoney = tmp; } } } coinMoney[i] = minMoney; } console.log(total, coinMoney); //2 [3,3] } MakeMoney([1,3,4],6);

解决:首先,要取出6块钱得到最优,可以看成是一个某一面值(k, k=1,3,4)的钱币 + 6 - k 的最优,同理 6-k 的最优可以看成 1 + 6-k-k的最优,也就是说,要求6元的最优 我们需要将 6元内所有可能的最优求出来,每一个可能都是一个子问题。
初始设置 coinMoney = [0] 代表取0元需要张钱币。
而后 首先求得 coinMoney[1] = coinMoney[0] + 1;为一张
也就是要取 1元 最优 等于 0元最优 + 1;

当然贪心算法的案例还有很多 比如活动选择问题 背包问题 多机调度问题

分治法

在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

这个技巧是很多高效算法的基础,如排序算法(快速排序、归并排序)、傅立叶变换(快速傅立叶变换)。

eg:快速排序

function quickSort(arr) { let len = arr.length; if(len<=1) return arr; let pivot = arr.splice(0,1)[0],left=[],right=[]; for(let i=0;i<len-1;i++){ if (arr[i] > pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } // 这里就体现了分治法的子问题合并 return [...quickSort(left),pivot,...quickSort(right)]; };

日本程序员norahiko,写的一个排序算法的动画演示

image.png