温故而知新:回溯 LeetCode22 、17

回溯思想个人理解:有条件的穷举,当该路径不满足条件后,就回溯,返回到上一步其他的路径查找答案。

例如:22 括号生成,我们可以利用穷举的方法,列出所有的可能情况,然后去掉不满足的情况;那么我们就要思考如何实现穷举呢?
  一般看到穷举,我们似乎可以有点规律的尝试回溯思想,使用递归来实现;然后,考虑去除不满足的情况,可以尝试在递归过程中,避免不满足情况的发生,我们可以利用两个数open,close来记录左右括号出现的次数,close<open ,open<n;

同样的17:电话号码的自由组合,也是一个需要穷举的题目,并且可以尝试使用回溯思想去完成;
  当我们选择一个号码后,就会有对应的几种字母出现,这个我们可以利用哈希表来得到结果;然后我们可以根据字母个数,画出不同的路径,任意一条路径下,选择了一个字母后,再选择下一个数字对应的某一个字母;
  边界条件:当我们用来存储字符串的string大小==n*2时,说明可以返回了;

回溯、dfs、递归之间的区别?
递归:就是自我调用,是一种方式,也是一种思想;
dfs:深度优先搜索,先往一个方向搜索到底,然后回升
回溯:是一种思想,就是搜索所有的可能,一旦出现不满足的情况,就回溯;可以说是隐式树的dfs

刷题总结类 文章被收录于专栏

这里记录一些刷题时候的总结思考

全部评论

相关推荐

dongsheng66:如果想进大厂的话,在校经历没必要占这么大篇幅,可以把专业技能单独放一个专栏写,可以加个项目经历
点赞 评论 收藏
分享
11-15 17:19
湖南大学 Java
成果成果成果果:这是哪个公司的hr,这么离谱吗,我没见过用性别卡技术岗的,身边女性同学拿大厂offer的比比皆是
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务