数据结构和算法躬行记(6)——贪心算法
贪心算法(Greedy Algorithm)会在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,不能回退,从而希望结果是最好或最优的算法。它是动态规划的一种特例,需要满足更多的限制条件。
贪心算法在有最优子结构的问题中尤为有效(例如求图的最小生成树、哈夫曼编码等),最优子结构是指局部最优解能决定全局最优解。即问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
一、区间调度
给定多个 [start, end] 的区间集合,算出有多少个不重叠的区间。例如 [1,3], [2,4], [3,6],有两个不重叠的区间 [1,3], [3,6],因为边界相互接触,并不算重叠。例题:435. 无重叠区间。
解题思路如下所列:
(1)根据终点对区间进行排列。
(2)从区间集合中选取一个终点最小的区间 [start, minEnd]。
(3)将所有与 [start, minEnd] 相交的区间从集合中移除。
(4)重复执行(2)和(3),直至遍历完集合。
具体实现代码如下所示。
function eraseOverlapIntervals(intervals) { intervals.sort((a, b) => a[1] - b[1]); let curEnd = intervals[0], //终点最小的区间 count = 1; //不重叠的区间数 intervals.forEach((value) => { if (value[0] < curEnd[1]) { //过滤起点比curEnd终点小的区间 return; } count++; curEnd = value; }); return count; }
二、分糖果
假设有 m 块糖果和 n 个小孩,但是 m > n,即糖果少,小孩多,会有一部分小孩分不到糖果。
每块糖果的大小不等,这 m 个糖果的大小分别是s1,s2,s3,……,sm。每个小孩最多分到一块糖果,并且每个小孩对糖果大小的需求也不同,他们的需求分别是g1,g2,g3,……,gn。
如果 sj >= gi ,那么可以将这个饼干 j 分配给小孩 i ,这个小孩会得到满足。该如何分配糖果,才能满足最多数量的小孩。例题:455. 分发饼干。
解题思路是每次从剩下的小孩中,找出对糖果需求最小的,然后发给他当前糖果中能满足他的最小糖果,如下所示。
function findContentChildren(g, s) { g.sort((a, b) => a - b); //升序排列 s.sort((a, b) => a - b); //升序排列 let n = 0, m = 0, count = 0; //满足的小孩人数 while (n < g.length && m < s.length) { if (g[n] <= s[m]) { //小孩能够得到满足 n++; m++; count++; continue; } m++; } return count; }
三、钱币找零
假设买一杯牛奶需要5元,顾客向你支付5 元、10 元或 20 元纸币,你需要判断是否能正确找零(开始时手头没有零钱)。例题:860. 柠檬水找零。
解题思路是先用面值最大的纸币来找零,不够的话再用更小一点的面值,直至完成找零或无法找零,如下所示。
function lemonadeChange(bills) { let five = 0, //5元纸币数量 ten = 0; //10元纸币数量 for (let bill of bills) { switch (bill) { case 5: five++; //增加5元纸币数量 break; case 10: if (five > 0) { //有5元才纸币能找零 five--; } else { return false; } ten++; break; case 20: if (five > 0 && ten > 0) { //用5元和10元两种纸币找零 five--; ten--; } else if (five >= 3) { //用3张5元纸币找零 five -= 3; } else { return false; } break; } } return true; }
相关文章
- 痞子衡嵌入式:关于做技术的工作态度方面的几点建议
- 痞子衡嵌入式:Ethos-U55,ARM首款面向Cortex-M的microNPU
- 痞子衡嵌入式:语音处理工具pzh-speech诞生记(2)- 界面构建(wxFormBuilder3.8.0)
- 1行Python代码,计算程序的运行时间,也可以用在算法和接口的调优上
- 必会的这15个Mysql优化问题,面试官、DBA都要高看你一眼,速度收藏
- 端面槽宏程序编程
- 前端一面高频面试题(附答案)
- 前端必会面试题汇总
- jsx和React.createElement是什么关系?面试常问
- 常见react面试题
- 社招前端二面react面试题集锦
- 设计分享|单片机双灯循环移动
- 常见经典vue面试题(面试必问)
- 常考vue面试题(附答案)
- 前端手写面试题合集
- 高级前端手写面试题指南
- 运营商未来看数字业务,数字业务未来看云计算,战争已经打响……
- 10万移动员工入网格,如何激励?
- 中国移动逆风飞翔的十年!
- 中国移动即将分拆上市是这家子公司?什么背景?