查看: 634|回复: 5
收起左侧

[Leetcode] 如何看出一个题有Greedy的解法

|只看干货
匿名用户-B29  2022-6-24 12:00:26 |阅读模式
本楼: 👍   100% (2)
 
 
0% (0)   👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
楼主目前也刷了近千题 周赛排名不太稳定有时候前800 有时候只有3-4千名。最近总结 发现一直对Greedy不是很敏感 碰上greedy很多时候看不出来。 想问问大家有没有什么理解 能够帮助到我们这些不太会利用greedy做题的人。

上一篇:个人的新手刷题经验
下一篇:求推荐的mock软件,除了pramp之外
66j 2022-6-24 12:26:47 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   98% (781)
 
 
1% (13)    👎
去codeforce上 刷一下greedy, constructive的tag。推荐难度1400 - 1800 的。

评分

参与人数 3大米 +5 收起 理由
生蚝来十个 + 1 赞一个
14417335 + 3 给你点个赞!
brad56 + 1 赞一个

查看全部评分

回复

使用道具 举报

yangff 2022-6-24 13:26:21 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   93% (154)
 
 
6% (11)    👎
本帖最后由 yangff 于 2022-6-24 00:49 编辑

最优化问题做题的话你的选择是很有限的,抛开数学题不谈,剩下的要么就是搜,要么就是dp,要么就是二分、分治,要么就是贪心(还有建图最大流之类的以及一些奇奇怪怪的暂且不谈吧)。
这里面搜的数据范围一般比较明显,除非是花样剪枝地,另外就是基本上就没有太好的结构或者性质
二分的话要能转化成判定性问题,并且判定的复杂的够低,并且可行解是连续的。
分治、dp和贪心在性质上很接近,和分治相比后两者的特征是可以划分出阶段,而分治则需要能够高效地合并解。
有了阶段就再看它递推的过程中是更容易合并状态还是更容易直接选出下一个状态。如果是贪心的话,因为决策的时候是盲目的,所以要么决策之间有很高的独立性,要么就是你稍微算算可以发现一边损失的可以再另一边补回来,所以每次按照单位收益最高选就行,再或者就是证明如果不按照贪心的顺序的解一定不是最优的诸如此类。。(Exchange Argument、拟阵这些的)。和dp的区别就是这里每个阶段不再需要尝试多个状态。反过来说,如果用DP做可能也可以,但是效率可能就有问题,或者压根就没法进行状态编码(比如状态可能是n!的而且没法合并)
当然这里只针对相对比较简单的问题。

评分

参与人数 2大米 +11 收起 理由
14417335 + 10 给你点个赞!
mhxzkhl + 1 赞一个

查看全部评分

回复

使用道具 举报

xiaokeishaobo35 2022-6-24 12:14:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (460)
 
 
1% (6)    👎
同疑惑,插个眼~
回复

使用道具 举报

地里的匿名用户
匿名用户-8DA  2022-6-24 13:41:03
本楼: 👍   0% (0)
 
 
0% (0)   👎
周赛3000-4000是只做了3题吗?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (1424)
 
 
5% (89)    👎
楼主贴几个不太懂的greedy的例子? 我greedy也不行… 蹲一个讨论
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表