一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请号
扫码关注留学申请公众号
查看: 4210|回复: 15
收起左侧

[Leetcode] 一个方法让你秒杀所有递归题

    [复制链接] |只看干货 |leetcode, 刷题
我的人缘0

升级   7.71%


分享帖子到朋友圈
Fireball | 显示全部楼层 |阅读模式
本楼: 👍   100% (18)
 
 
0% (0)   👎
全局: 👍   98% (58)
 
 
1% (1)    👎

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

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

x
不好意思标题党了🐶,这个帖子主要用来总结我在FLAG几年工作中学习到关于API Design中我个人认为最重要的一个原则以及在刷题过程中的应用。再次刷leetcode,这条原则给了我完全不同的感受。

tl;dr   Principle: Contract First

关于Contract First API Design,这个link可以给大家一些介绍。总结起来就是在coding之前要 1)把问题拆成明确的子模块,并 2)用明确的Contract(合约)描述各个模块API接口提供的功能。这一点和算法中的递归概念不谋而合。在递归中我们会 1)明确定义问题与可以被分解的子问题,2)假设子问题可以被解决,考虑如何把子问题合并解决原问题,3)明确递归终止/边境条件。我们可以看到递归问题的解决只是比Contract design多需要思考如何终止递归 3)这一步骤,逻辑上它们非常一致。下面我拿leetcode的两个不同难度的题举例说明一下,解释都在leetcode discussion的comment里。

LC 114. Flatten Binary Tree to Linked List (Medium)
Solution

LC 124. Binary Tree Maximum Path Sum (Hard)
Solution

在这个过程中,有两点应该值得参考。
  (1)在考虑子问合并解决原问题时不要去考虑递归终止条件。把注意力集中在“假设我能够通过call这个递归函数解决子问题,我怎么能通过子问题解决原问题”。例如LC114中,要关注的问题是假设我已经能把左子树或者右子树flatten,我如何把flatten好的链表组合起来形成符合要求的新链表。
  (2)API Contract来源于在思考(1)问题时解决原问题需要的信息。例如在LC114中,可以发现假设解决了子问题后只返回root结点是不够的,这时候我们需要让它返回flatten后的tail结点方便左右子树同时存在时的处理。

我自己觉得这个思维模式不仅适用与递归方法也同样适用于DP之类的其它题型。大家觉得有用的话请加加米啦。还是有很多帖子没有米看不了,谢谢大家。如果还有什么问题欢迎留言一起探讨。

评分

参与人数 26大米 +78 收起 理由
victorz90 + 2 给你点个赞!
大队管理员 + 30 欢迎分享你知道的情况,会给更多积分奖励!
dreamdriver + 2 很有用的信息!
Archliner + 3 给你点个赞!
TravisLiang + 1 恩比德點了贊
zhang5690889 + 1 赞一个
324353664 + 1 赞一个
不要拧巴 + 2 很有用的信息!

查看全部评分


上一篇:自主学习
下一篇:关于formal method

本帖被以下淘专辑推荐:

我的人缘0

升级   56.5%

本楼: 👍   100% (23)
 
 
0% (0)   👎
全局: 👍   98% (54)
 
 
1% (1)    👎
从另一个角度看递归的本质:信任

Let’s trust the process

评分

参与人数 5大米 +8 收起 理由
yeehaah + 1 赞一个
surpicture + 2 很有用的信息!
fuqing04 + 1 赞一个
Fireball + 1 赞一个
车车车车车 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   34%

litJordan 2020-11-25 10:56:29 | 显示全部楼层
本楼: 👍   100% (8)
 
 
0% (0)   👎
全局: 👍   100% (62)
 
 
0% (0)    👎
还有一个小tip: solve或者debug 递归的时候,大忌就是去人脑压栈,去一层层往下再往上的套,这样非常容易就乱了。就想前面几楼说的, trush the process。相信子问题是一个已经被解决的状态,怎么通过这个子问题来解决当前问题。最后base case也就是结束条件搞清楚了就完全没问题了。LC的各种backtracking,tree的dfs几乎都是这样的套路。

评分

参与人数 1大米 +1 收起 理由
yeehaah + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0

升级   4.68%

qiuqiushasha 2020-11-25 04:18:42 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   94% (1252)
 
 
5% (67)    👎
我的方法是套模板 常规的dp 无外乎 array上一维O(n)或者二维O(n2) 甚至再在ij中间再遍历一一遍k  
或者就是以某个数值为cut off 找答案 然后遍历 找min/max等等
或者就是dfs再加上记忆化 这个从前往后推 更容易

我一般都是套模板 看哪个模板能用 只要模板找对了  基本这个题就一马平川了

做dp时 我个人一直强迫自己要想high level 不要想细节
回复

使用道具 举报

我的人缘0

升级   61%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (64)
 
 
0% (0)    👎
谢谢分享,码住
回复

使用道具 举报

我的人缘0

升级   35.86%

ci-hanker 2020-11-24 21:12:20 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (380)
 
 
2% (10)    👎
感谢分享,收藏
回复

使用道具 举报

我的人缘0

升级   69.5%

Mel_Mellow 2020-11-25 02:48:37 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
明确记住本层的问题是什么,只考虑本层,剩下的交给字问题处理。
回复

使用道具 举报

我的人缘0

升级   7.71%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (58)
 
 
1% (1)    👎
qiuqiushasha 发表于 2020-11-24 12:18:42
我的方法是套模板 常规的dp 无外乎 array上一维O(n)或者二维O(n2) 甚至再在ij中间再遍历一一遍k  
或者就是以某个数值为cut off 找答案 然后遍历 找min/max等等
强迫想high level很重要,接口定义好后所有的都是implementation detail可以放在后面想。一些层次比较清晰的题每一步不光接口可以很清晰,时间空间复杂度也可以很清晰。
回复

使用道具 举报

我的人缘0

升级   36%

阿咧 2020-11-25 09:31:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
码了 谢谢分享
回复

使用道具 举报

我的人缘0

升级   29%

johnHao 2020-11-25 10:40:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (159)
 
 
3% (6)    👎
楼主这题刷的确实有意义
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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