前言
在前端开发过程中，除了一般的逻辑使用之外，也会涉及到算法相关的知识，比如冒泡排序、数组去重/合并、贪心算法、八皇后算法等等，这些都是比较常用的前端算法相关的知识点。关于前端实际开发中用到的算法，虽然没有后端要求的那么多，但是也有比较重要的算法知识，本篇博文就来分享一下关于贪心算法的相关知识点，记录一下，方便查阅使用。
贪心算法概念
贪心算法（又叫贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。（注意： 贪心算法，算法结构犹如其名，以局部最优解，进行小范围的最优累加，但是贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。）
贪心算法的构成
贪心算法的构成有：霍夫曼编码、prim和kruskal最小生成树算法、Dijkstra最短路径算法。
贪心算法的核心
贪心算法的核心主要是要找出问题的贪心策略，贪心策略的主要逻辑就是每一次都选择当前的最优解，一直到得出全局的最优解。
贪心算法的缺点
虽然贪心算法每一次都选择当前的最优解，直到得出全局的最优解，但每一次的局部最优解不等于最终的全局最优解，不能从整体考虑所有的可能，每次都是采用局部的最优解、不回溯，所以有时候无法得出最优解，这就是贪心算法最大的缺点！
贪心算法的应用场景
贪心算法的应用场景：1、关于某一组数据，需要有限制值和期望值，想要从中选出几个数据，在满足前面限制值的情况下，期望值最大； 2、每次选择当前条件下，在对限制值同等贡献的情况下，对期望值贡献最大的数据；3、买卖产品的最佳时机；4、分水果、分饼干、分办公用具等分配问题。
贪心算法的使用步骤
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，贪心算法一般按如下思路步骤使用：
- 建立数学模型来描述问题；
- 把求解的问题分成若干个子问题；
- 对每个子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来解问题的一个解。
具体的示例如下所示：
Greedy(Q) { //Q是问题的输入集合，也就是候选集合
C={ }; //初始解集合是一个空集合
while (not solution(C)) { //集合C没有构成问题的一个解
x=select(Q); //在候选集合Q中做贪心选择
if feasible(C, x) //判断集合C中加入x后的解是否可行
C=C+{x};
Q=Q-{x};
}
return C;
}贪心算法的示例
这里列举两个比较有代表性的贪心算法示例，方便理解使用。
示例一：分水果、分饼干、分办公用具等分配问题———分饼干问题
/**
* @param {number[]} h 胃口值
* @param {number[]} m 饼干的大小
* @return {number} i 最优解
*/
var findCookies = function(h, m) {
const mysort = (a, b) => {
return a-b;
}
h.sort(mysort);
m.sort(mysort);
let i = 0;
m.forEach((n) => {
if(n >= h[i]){
i++;
}
})
return i;
};
示例二：买卖产品的最佳时机——————买卖股票的最佳时机
/**
* @param {number[]} p 价格
* @return {number} r 最优解
*/
var maxOptimal = function(p) {
var r = 0;
for(var i=1;i<=p.length;i++){
if(p[i]>p[i-1]){
r = p[i] - p[i-1] + r;
}
}
return r;
};
示例三：柠檬水找零——每一杯柠檬水的售价为 5元。每位顾客只买一杯柠檬水，然后付5元或10元或 20元，然后给每个顾客正确找零。
var priceChange = function (rmbs) { //若客户给了20，可以找10+5，或5+5+5，其中10+5就算是贪心
let fiveN = 0; //5元0张
let tenN = 0; //10元0张
for (let i = 0; i < rmbs.length; i++) {
let rmb = rmbs[i]; //第i个客户给了张多少元的钱
if (rmb === 5) {
fiveN += 1;
} else if (rmb === 10) {
//客户给10元+，有5元找-，找不开直接false
if (fiveN > 0) {
fiveN -= 1;
tenN += 1;
} else {
return false;
}
} else {
//客户给20
if (tenN >= 1 && fiveN >= 1) {
//优先找零组合10+5
fiveN -= 1;
tenN -= 1;
} else if (fiveN >= 3) {
//接着找找零组合5+5+5
fiveN -= 3;
} else {
return false;
}
}
}
return true;
};
示例四：区间覆盖——假设有n个区间，区间的起始断点和结束断点分别是[a1,b1],[a2,b2],….[an,bn]，从这些区间中选出一部分区间，使这部分区间满足两两不想交，最多能选出的区间个数。
var sArray = function(array){
let m = array.length;
let sizeArray = array.sort(compareA());
let res = [],c = 0,d = 0;
for(let i = 0;i<m;i++){
let left = sizeArray[i][0];
let right = sizeArray[i][1];
if(left>d || right<c){
res.push(sizeArray[i]);
c = left;
d = right;
}
}
return res;
}
var compareA = function(){
return function(a,b){
var value1 = a[1];
var value2 = b[1];
return value1 - value2;
}
}
let array = [
[6,8],
[2,4],
[5,9],
[1,5],
[9,10],
[3,5]
]
console.log(sArray(array)) //输出结果为 [2,4], [6,8],[9,10]
最后
通过本文关于前端开发中JS中使用到的贪心算法场景的汇总的介绍，虽然在大部分实际开发中使用到上述示例的可能性不大，但是还是要掌握对应的知识点，尤其是在求职面试过程中会涉及到前端相关的算法知识使用，所以还是要学会掌握的，尤其是从事前端开发不久的开发者来说尤为重要，是一篇值得阅读的文章，且在实际开发中也是必用知识点，所以说这个知识点是必备的，重要性就不在赘述。欢迎关注，一起交流，共同进步。
