失眠网,内容丰富有趣,生活中的好帮手!
失眠网 > 【LeetCode刷题】Greedy贪心算法笔记

【LeetCode刷题】Greedy贪心算法笔记

时间:2019-06-02 18:07:54

相关推荐

【LeetCode刷题】Greedy贪心算法笔记

题目特点?-怎么判断一道题适合使用greedy?

“最”–付出最少,得到最多->贪心是目的:想用最少的投入获得最大回报“给后面的选择留下最大余地,能确保全局最优”

解题思路?

流程:

局部最优 => 前面的选择给后面的选择留下最大余地(比如:留下尽可能多的饼干||留下尽可能大的区间||需求最小的得到的最少)

能确保全局最优(也就是结果正确)

(逻辑自洽:如果我不留下尽可能多的饼干->也就是说新方案饼干减少,其他不变,那么能吃饱的人肯定会不变或减少->非最优方案;如果不留下尽可能大的区间->后面的区间更可能和前面的重叠,需要移除更多->非最优方案)

思路:

首先,顺序问题:先满足最容易满足的(最容易吃饱的/最可能不被剔除的……)

和整体比较:排序–455 435和附近比较(相邻的两个):赋初值+正反遍历两次–135CPP sort?

其次,局部最优:满足&&留下最大余地

最后,按照次序遍历,直至最后(结果已出/遍历完成)

cpp iterate on vector?

例题:

如果觉得《【LeetCode刷题】Greedy贪心算法笔记》对你有帮助,请点赞、收藏,并留下你的观点哦!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。